Description

存在如下递推式:

F(n+1)=A1*F(n)+A2*F(n-1)+…+An*F(1)

F(n+2)=A1*F(n+1)+A2*F(n)+…+An*F(2)

…

求第K项的值对1000000007取模的结果

Input

单组测试数据

第一行输入两个整数 n , k (1<=n<=100,n < k<=10000000000)

第二行输入 n 个整数 F(1) F(2) … F(n)

第三行输入 n 个整数A1 A2 … An

Output

输出一个整数

Sample Input

2 3

1 2

3 4

Sample Output

10

【题目链接】:http://oj.acmclub.cn/problem.php?cid=1162&pid=5

【题意】

【题解】



一道裸的矩阵乘法题;

构造一个系数矩阵

0       1       0    ...    0

0       0       1    ...    0

...

0       0       0    ...    1

a[n]    a[n-1]  a[n-2]...   a[1]

(这个矩阵每乘一次(f[1],f[2],f[3]…f[n])就会往后递推一个n)



对于k>n的询问

求这个矩阵的(k-n)次幂;

然后把最后的矩阵的最后一行依次乘上f[1],f[2]…f[n]相加;

就是f[k]了;



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

const int G = 100;       //矩阵大小

const LL MOD = 1e9 + 7;    //模数

struct MX

{

    int v[G+5][G+5];

    void O() { ms(v, 0); }

    void E() { ms(v, 0); for (int i = 1; i <= G; ++i)v[i][i] = 1; }

    void P()

    {

        for (int i = 1; i <= G; ++i)

        {

            for (int j = 1; j <= G; ++j)printf("%d ", v[i][j]); puts("");

        }

    }

    MX operator * (const MX &b) const

    {

        MX c; c.O();

        for (int k = 1; k <= G; ++k)

        {

            for (int i = 1; i <= G; ++i) if (v[i][k])

            {

                for (int j = 1; j <= G; ++j)

                {

                    c.v[i][j] = (c.v[i][j] + (LL)v[i][k] * b.v[k][j]) % MOD;

                }

            }

        }

        return c;

    }

    MX operator + (const MX &b) const

    {

        MX c; c.O();

        for (int i = 1; i <= G; ++i)

        {

            for (int j = 1; j <= G; ++j)

            {

                c.v[i][j] = (v[i][j] + b.v[i][j]) % MOD;

            }

        }

        return c;

    }

    MX operator ^ (LL p) const

    {

        MX y; y.E();

        MX x; memcpy(x.v, v, sizeof(v));

        while (p)

        {

            if (p&1) y = y*x;

            x = x*x;

            p>>=1;

        }

        return y;

    }

}xishu;

int n;

LL k,f[N],a[N];

int main(){

    //Open();

    Close();

    cin >> n >> k;

    rep1(i,1,n) cin >> f[i];

    rep1(i,1,n) cin >> a[i];

    rep1(i,1,n) xishu.v[n][i] = a[n-i+1];

    rep1(i,1,n-1) xishu.v[i][i+1] = 1;

    if (k<=n){

        cout << f[k]%MOD << endl;

        return 0;

    }

    xishu = xishu^(k-n);

    LL ans = 0;

    rep1(i,1,n)

        ans = (ans + xishu.v[n][i]*f[i])%MOD;

    cout << ans << endl;

    return 0;

}