UVA10870矩阵快速幂与递推公式的关系

 1 /*UVA10870：
 2 矩阵快速幂与递推公式的关系：关键就是这句话，以后做题能联想到即可
 3 f(n)=a1f(n-1)+...adf(n-d)
 4 */
 5 #include<iostream>
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<algorithm>
 9 #include<stdlib.h>
10 #include<math.h>
11 #include<queue>
12 #include<vector>
13 #include<map>
14 #define ULL unsigned long long
15 #define LL long long
16 #define Max_size 17
17 
18 using namespace std;
19 
20 int d,n,MOD;//
21 struct Mat
22 {
23     LL mat[Max_size][Max_size];
24 
25 };
26 Mat operator*(Mat a,Mat b)
27 {
28     Mat c;
29     memset(c.mat,0,sizeof(c.mat));
30     for (int i=0;i<d;i++)
31         for (int j=0;j<d;j++)
32             for (int k=0;k<d;k++)
33                 if (a.mat[i][k] && b.mat[k][j])
34                    c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
35     return c;
36 }
37 Mat operator+(Mat a,Mat b)
38 {
39     Mat c;
40     memset(c.mat,0,sizeof(c.mat));
41     for (int i=0;i<d;i++)
42         for (int j=0;j<d;j++)
43             c.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%MOD;
44     return c;
45 }
46 Mat E;
47 
48 void builtE()
49 {
50     memset(E.mat,0,sizeof(E.mat));
51     for (int i=0;i<Max_size;i++)
52     {
53         E.mat[i][i]=1;
54     }
55 }
56 Mat operator^(Mat A,int x)
57 {
58     Mat c;
59     builtE();
60     c=E;
61     for ( ; x; x>>=1)
62     {
63         if ( x & 1)
64             c = c * A;
65         A = A * A;
66     }
67     return c;
68 }
69 Mat K,F;
70 int main()
71 {
72     while(cin>>d>>n>>MOD)
73     {
74         memset(K.mat,0,sizeof(K.mat));
75         memset(F.mat,0,sizeof(F.mat));
76         for(int i=d-1;i>=0;i--) cin>>K.mat[i][d-1];
77         for(int i=0;i<d;i++) K.mat[i+1][i]=1;
78         K=K^(n-1);
79         for(int i=0;i<d;i++) cin>>F.mat[0][i];
80         F=F*K;
81         cout<<F.mat[0][0]<<endl;
82     }
83     return 0;
84 }