很水的一道矩阵快速幂。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define ll long long 5 using namespace std; 6 int g[10],k,mod; 7 struct rec{ 8 ll v[10][10]; 9 rec(){memset(v,0,sizeof v);} 10 }; 11 rec mul(rec a,rec b){ 12 rec ans; 13 ll sum; 14 for(int k=0;k<10;k++){ 15 for(int i=0;i<10;i++){ 16 for(int j=0;j<10;j++){ 17 sum=a.v[i][k]*b.v[k][j]%mod; 18 ans.v[i][j]=(ans.v[i][j]+sum)%mod; 19 } 20 } 21 } 22 return ans; 23 } 24 rec pow(rec a,int n){ 25 if(n==1) return a; 26 rec ans=pow(a,n/2); 27 ans=mul(ans,ans); 28 if(n&1) return mul(ans,a); 29 else return ans; 30 } 31 int f(rec a){ 32 int ret=0; 33 for(int i=0;i<10;i++){ 34 ret=(ret+a.v[0][i]*(9-i)%mod)%mod; 35 } 36 return ret; 37 } 38 int main(){ 39 while(~scanf("%d%d",&k,&mod)){ 40 if(k<10) {printf("%d ",k);continue;} 41 for(int i=0;i<10;i++) scanf("%d",&g[i]); 42 rec a; 43 for(int i=0;i<10;i++) a.v[0][i]=g[i]; 44 for(int i=1;i<10;i++) a.v[i][i-1]=1; 45 a=pow(a,k-9); 46 printf("%d ",f(a)); 47 } 48 return 0; 49 }