hdu1757 A Simple Math Problem

Problem Description

Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 *
f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0
or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and
could you help Lele to caculate f(k)%m.

 

Input

The problem contains mutiple test cases.Please process
to the end of file.
In each case, there will be two lines.
In the first
line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5
)
In the second line , there are ten integers represent a0 ~ a9.

 

Output

For each case, output f(k) % m in one line.

 

Sample Input

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

 

Sample Output

45
104

/*

裸题

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = ;

ll sz,mod,f[maxn],a[maxn],ans[maxn];

struct mtx{

    ll v[maxn][maxn];

    void clear(){

        memset(v,,sizeof(v));

    }

    mtx mul(mtx A,mtx B){

        mtx C;

        C.clear();

        for(int i = ;i <= sz;i++){

            for(int j = ;j <= sz;j++){

                for(int k = ;k <= sz;k++){

                    C.v[i][j] = (C.v[i][j] + A.v[i][k]*B.v[k][j]) % mod;

                }

            }

        }

        return C;

    }

    mtx pow(mtx A,int n){

        mtx R;

        R.clear();

        for(int i = ;i <= sz;i++) R.v[i][i] = ;

        while(n){

            if(n&) R = R.mul(R,A);

            n >>= ;

            A = A.mul(A,A);

        }

        return R;

    }

    void get_tr(mtx A){

        for(int i = ;i <= sz;i++){

            for(int j = ;j <= sz;j++){

                ans[j] = (ans[j] + f[i]*A.v[i][j]) % mod;

            }

        }

    }

};

int main(){

    ll d,n,m;

   while(scanf("%I64d%I64d",&n,&m) == ) {

       d = ;

       mtx A;

    for(int i = ; i <= d; i++) { cin >> a[i]; a[i] %= m; }

    for(int i = d; i >= ; i--) { f[i] = d-i; f[i] %= m; }

    if(n < ){

        cout<<n<<endl;

        continue;

    }

    n++;

    A.clear();

    memset(ans,,sizeof(ans));

    for(int i = ; i <= d; i++) A.v[i][] = a[i];

    for(int i = ; i <= d; i++) A.v[i-][i] = ;

    sz = d;

    mod = m;

    A = A.pow(A,n-d);

    A.get_tr(A);

    cout << ans[] << endl;

  }

    return ;

}