hdu 1757【A Simple Math Problem】

矩阵相乘
代码如下：
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 struct matrix
 5 {
 6     int g[10][10];
 7 }mt;
 8 
 9 int kk,m;
10 
11 matrix multi(matrix a,matrix b)
12 {
13     matrix ans;
14 
15     for(int i = 0;i < 10;i ++)
16     {
17         for(int j = 0;j < 10;j ++)
18         {
19             int t = 0;
20             for(int u = 0;u < 10;u ++)
21             {
22                 t += a.g[i][u] * b.g[u][j];
23                 t = t % m;
24             }
25             ans.g[i][j] = t % m;
26         }
27     }
28 
29     return ans;
30 }
31 
32 int solve(int k)
33 {
34     matrix temp = mt;
35     matrix ans;
36     memset(ans.g,0,sizeof(ans.g));
37     for(int i = 0;i < 10;i ++)
38     {
39         ans.g[0][i] = i;
40     }
41 
42     for(int i = 0;k != 0;i ++)
43     {
44         if(k & (1 << i))
45             ans = multi(ans,temp);
46         temp = multi(temp,temp);
47         k = k & (~(1 << i) );
48     }
49 
50     return ans.g[0][9];
51 }
52 
53 int main()
54 {
55     while(scanf("%d%d",&kk,&m) == 2)
56     {
57         memset(mt.g,0,sizeof(mt.g));
58         for(int i = 0;i < 10;i ++)
59         {
60             int a;
61             scanf("%d",&a);
62             mt.g[9 - i][9] = a;
63             if(i < 9)
64             mt.g[9 - i][8 - i] = 1;
65         }
66 
67         if(kk < 10)
68         {
69             printf("%d\n",kk % m);
70             continue;
71         }
72 
73         printf("%d\n",solve(kk-9)%m);
74     }
75 
76     return 0;
77 }