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.
构造一个矩阵
{
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
}得解
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <math.h>
using namespace std;
typedef long long LL;
const int maxn=;
int MOD;
struct Matrix
{
LL m[maxn][maxn];
Matrix mult(Matrix &rhs)
{
Matrix ans;
for(int i=; i<; i++)
for(int j=; j<; j++)
{
ans.m[i][j]=;
for(int k=; k<; k++)
ans.m[i][j]=(ans.m[i][j]+(m[i][k]*rhs.m[k][j])%MOD )%MOD; }
return ans;
}
};
int a[];
void powk(int n)
{
Matrix A,ans;
memset(ans.m,,sizeof(ans.m));
memset(A.m,,sizeof(A.m));
for(int i=; i<; i++){
ans.m[i][i]=;
A.m[][i]=a[i];
A.m[i+][i]=;
}
while(n)
{
if(n&)ans=ans.mult(A);
n>>=;
A=A.mult(A);
}
LL AS=;
for(LL i=; i<; i++){
AS=(AS+(ans.m[][i]*(-i+))%MOD )%MOD;
}
printf("%I64d\n",AS);
}
int main()
{
int k;
while(scanf("%d%d",&k,&MOD)==)
{
for(int i=; i<; i++)scanf("%d",&a[i]);
if(k<){
printf("%d\n",k%MOD); continue;
}
powk(k-);
}
return ;
}