http://acm.hdu.edu.cn/showproblem.php?pid=1757
思路：矩阵快速幂 ，通过化简，得出下面公式：
所以主要的问题就是求出中间矩阵的n-9次方，设中间矩阵为A
那么A^n-9可以通过快速幂求出来，比如 A^10=A^(1010)=A^8*A^2（只需要计算5次）。
核心代码：
matrix matrix_quick_power(matrix a,int k)//矩阵快速幂0.0 { matrix b; memset(b.mat,0,sizeof(b.mat)); for(int i=0;i<10;i++) b.mat[i][i]=1;//单位矩阵b while(k) { if(k%2==1) b=matrix_mul(a,b); a=matrix_mul(a,a); k/=2; } return b; }完整代码：
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int n,mod; struct matrix { int mat[10][10]; }A,B; matrix matrix_mul(matrix a,matrix b) { matrix c; memset(c.mat,0,sizeof(c.mat)); int i,j,k; for(int i=0;i<10;i++) for(int j=0;j<10;j++) for(int k=0;k<10;k++) c.mat[i][j]+=a.mat[i][k]*b.mat[k][j],c.mat[i][j]%=mod; return c; } matrix matrix_quick_power(matrix a,int k)//矩阵快速幂0.0 { matrix b; memset(b.mat,0,sizeof(b.mat)); for(int i=0;i<10;i++) b.mat[i][i]=1;//单位矩阵b while(k) { if(k%2==1) b=matrix_mul(a,b); a=matrix_mul(a,a); k/=2; } return b; } int main() { while(~scanf("%d%d",&n,&mod)) { for(int i=0;i<10;i++) scanf("%d",&A.mat[0][i]); for(int i=1;i<10;i++) A.mat[i][i-1]=1; B=matrix_quick_power(A,n-9); int sum=0; for(int i=0;i<10;i++) sum+=B.mat[0][i]*(10-i-1),sum%=mod; printf("%d\n",sum); } }