继续填坑……链接：http://cogs.pro/cogs/problem/problem.php?pid=1493
题意：给出一个递推式：$f(n)=a[1]*f(n-1)+a[2]*f(n-2)+a[3]*f(n-3)+...+a[d]*f(n-d)$，求$f(n)$。
明显的矩阵推法……但是对于矩阵并不是很熟悉，所以自己打一发……
矩阵大概就是这个样子：
（公式炸了……）
然后快速幂就好了……
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int mod,d,n; 7 struct matrix 8 { 9 long long a[20][20]; 10 matrix(){memset(a,0,sizeof(a));} 11 matrix operator *(const matrix &b)const 12 { 13 matrix c; 14 for(int i=1;i<=15;i++) 15 for(int j=1;j<=15;j++) 16 for(int k=1;k<=15;k++)c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%mod; 17 return c; 18 } 19 }; 20 matrix qpow(matrix x,int tim) 21 { 22 matrix c=x,tmp; 23 for(int i=1;i<=15;i++)tmp.a[i][i]=1; 24 for(;tim;tim>>=1,c=c*c) 25 if(tim&1)tmp=tmp*c; 26 return tmp; 27 } 28 int haha() 29 { 30 freopen("recurrences.in","r",stdin); 31 freopen("recurrences.out","w",stdout); 32 while(scanf("%d%d%d",&d,&n,&mod)!=EOF&&d&&&n&&mod) 33 { 34 matrix a,b; 35 for(int i=1;i<=d;i++)scanf("%d",&a.a[1][i]); 36 for(int i=2;i<=d;i++)a.a[i][i-1]=1; 37 for(int i=1;i<=d;i++)scanf("%d",&b.a[d-i+1][1]); 38 if(n<=d) 39 { 40 printf("%d ",b.a[d-n+1][1]); 41 continue; 42 } 43 printf("%d ",(qpow(a,n-d)*b).a[1][1]); 44 } 45 } 46 int sb=haha(); 47 int main(){;}