---

<font color = red , size = '4'>下列图表转载自

链接：

题意：给出递推关系，求 f(k) % m 的值，

思路：

• 因为 k<2 * 10^9 , m < 10^5，O(n)算法应该是T掉了，当 k >= 10 时 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)，可以理解为这是两个行列是乘积的值，经下面分析可知用矩阵快速幂可搞

• 下列三个表分别命名为矩阵0，矩阵1，矩阵2。

fk	0	0	0	0	0	0	0	0	0
fk-1	0	0	0	0	0	0	0	0	0
fk-2	0	0	0	0	0	0	0	0	0
fk-3	0	0	0	0	0	0	0	0	0
fk-4	0	0	0	0	0	0	0	0	0
fk-5	0	0	0	0	0	0	0	0	0
fk-6	0	0	0	0	0	0	0	0	0
fk-7	0	0	0	0	0	0	0	0	0
fk-8	0	0	0	0	0	0	0	0	0
fk-9	0	0	0	0	0	0	0	0	0

等于

a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
1	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	1	0	0	0	0
0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	0	1	0

乘以

fk-1	0	0	0	0	0	0	0	0	0
fk-2	0	0	0	0	0	0	0	0	0
fk-3	0	0	0	0	0	0	0	0	0
fk-4	0	0	0	0	0	0	0	0	0
fk-5	0	0	0	0	0	0	0	0	0
fk-6	0	0	0	0	0	0	0	0	0
fk-7	0	0	0	0	0	0	0	0	0
fk-8	0	0	0	0	0	0	0	0	0
fk-9	0	0	0	0	0	0	0	0	0
fk-10	0	0	0	0	0	0	0	0	0

• 经过观察发现，当 k >= 10 时 f(k) = [ 矩阵1 ]^(k-9) * [ 矩阵2 ]

---

/*************************************************************************    > File Name: hdu1757.cpp    > Author:    WArobot     > Blog:      http://www.cnblogs.com/WArobot/     > Created Time: 2017年05月02日 星期二 19时25分30秒 ************************************************************************/#include
    
     using namespace std;const int maxn = 11;int MOD;#define ll long long #define mod(x) ((x)%MOD)struct mat{    int m[maxn][maxn];}unit;int n;mat operator * (mat a,mat b){    mat ret;    ll x;    for(int i=0;i<10;i++){        for(int j=0;j<10;j++){            x = 0;            for(int k=0;k<10;k++)                x += mod( (ll)a.m[i][k]*b.m[k][j] );            ret.m[i][j] = mod(x);        }    }    return ret;}// 初始化单位阵void init_unit(){    for(int i=0;i<10;i++)           unit.m[i][i] = 1;    return;}mat pow_mat(mat a,ll x){    mat ret = unit;    while(x){        if(x&1) ret = ret*a;        a = a*a;        x >>= 1;    }    return ret;}int main(){    mat a , f;    int aa[10];    ll  k;    init_unit();    memset(f.m,0,sizeof(f.m));    for(int i=0;i<10;i++)   f.m[i][0] = 9-i;    while(cin>>k>>MOD){        for(int i=0;i<10;i++)   cin>>aa[i];        if(k<10)    printf("%lld\n",k);        else{            // 构建a矩阵            for(int j=0;j<10;j++)   a.m[0][j] = aa[j];            for(int i=1;i<10;i++){                for(int j=0;j<10;j++){                    if(j+1==i)  a.m[i][j] = 1;                    else        a.m[i][j] = 0;                }            }            mat ans = pow_mat(a,k-9);            ans = ans*f;            printf("%d\n",ans.m[0][0]%MOD);        }    }    return 0;}