题目链接：链接。。。。

思路：就是构造一个矩阵

f[n]=a1*f[n-1]+a2*f[n-2]+...+ad*f[n-d];
由于n太大，不能直接递推，需要用矩阵快速幂来解决，时间复杂度为O(d^3logn)
举例，d=5的矩阵关系式为：
|a1 a2 a3 a4 a5| | f[n] | | f[n+1] |
|1 | | f[n-1] | | f[n] |
| 1 | * | f[n-2] | = | f[n-1] | (空白处为0)
| 1 | | f[n-3] | | f[n-2] |
| 1 | | f[n-4] | | f[n-3] |

code：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long LL; struct matrix { LL x[20][20]; friend matrix operator*(matrix &a,matrix &b); friend matrix operator^(matrix a,LL b); }; int n,d; LL mod; matrix operator*(matrix &a,matrix &b) //矩阵乘法 { int i,j,k; matrix c; for(i=1;i<=d;i++) { for(j=1;j<=d;j++) { c.x[i][j]=0; for(k=1;k<=d;k++) { c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%mod)%mod; } } } return c; } matrix operator^(matrix a,LL k) //矩阵快速幂 { matrix unit; memset(unit.x,0,sizeof(unit.x)); for(int i=0;i<20;i++) unit.x[i][i]=1; while(k) { if(k&1) unit=unit*a; a=a*a; k=k/2; } return unit; } matrix S,F; int main(int argc, char const *argv[]) { while(scanf("%d%d%lld",&d,&n,&mod)==3) { if(d==0&&n==0&&mod==0) break; int i; memset(S.x,0,sizeof(S.x)); for(i=2;i<=d;i++) { S.x[i][i-1]=1; } for(i=1;i<=d;i++) { scanf("%lld",&S.x[1][i]); S.x[1][i]%=mod; } memset(F.x,0,sizeof(F.x)); for(i=d;i>0;i--) { scanf("%lld",&F.x[i][1]); F.x[i][1]%=mod; } S=S^(n-d); F=S*F; printf("%lld\n",F.x[1][1]%mod); } return 0; }