题意：函数f(x),
若 x < 10 f(x) = x.
若 x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
且 ai(0<=i<=9) 仅为 0 或 1 .
给定k,m,求f(k)%m;
思路：求一个递推函数的函数值，显然是矩阵快速幂，矩阵构造方法如下：
#include#include #include using namespace std;typedef struct node{ int matrix[55][55];}Matrix;Matrix a,sa,unit;int n,k,t,mm;int num[50005];Matrix add(Matrix a,Matrix b){ int i,j; Matrix c; for(i=0;i<10;i++) { for(j=0;j<10;j++) { c.matrix[i][j]=a.matrix[i][j]+b.matrix[i][j]; c.matrix[i][j]%=mm; } } return c;}Matrix mul(Matrix a,Matrix b){ int i,j,h; Matrix c; for(i=0;i<10;i++) { for(j=0;j<10;j++) { c.matrix[i][j]=0; for(h=0;h<10;h++) { c.matrix[i][j]=c.matrix[i][j]+(a.matrix[i][h]*b.matrix[h][j]); c.matrix[i][j]%=mm; } } } return c;}Matrix cal(int e){ Matrix p,q; p=a,q=unit; while(e!=1) { if(e&1) { e--; q=mul(p,q); } else { e/=2; p=mul(p,p); } } p=mul(p,q); return p;}Matrix sum(int k){ Matrix temp,tnow; if(k==1) return a; temp=sum(k/2); if(k&1) { tnow=cal(k/2+1); temp=add(temp,mul(temp,tnow)); temp=add(temp,tnow); } else { tnow=cal(k/2); temp=add(temp,mul(temp,tnow)); } return temp;}int main(){ int i,j,ss,ans; while(scanf("%d%d",&k,&mm)!=EOF) { memset(num,0,sizeof(num)); memset(a.matrix,0,sizeof(a.matrix)); for(i=0;i<10;i++) { scanf("%d",&a.matrix[0][i]); unit.matrix[i][i]=1; if(i<9) a.matrix[i+1][i]=1; } if(k<10) { printf("%d\n",k%mm);continue; } sa=cal(k-9);//先求构造矩阵的k-9次方 ans=0; for(i=0;i<10;i++) { ans+=sa.matrix[0][i]*(9-i); ans%=mm; } printf("%d\n",ans); } return 0;}