HDU1575 Tr A

解题思路：矩阵快速幂模板题，见代码：
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 15;
 6 #define mod 9973
 7 int t, n, k;
 8 
 9 struct MT{
10     int m[maxn][maxn];
11 };
12 
13 MT Mul(MT a, MT b)
14 {
15     MT res;
16     memset(res.m, 0, sizeof(res.m));
17     for(int i = 0; i < n; i++)
18     {
19         for(int j = 0; j < n; j++)
20         {
21             for(int k = 0; k < n; k++)
22             {
23                 res.m[i][j] += a.m[i][k]*b.m[k][j] % mod;
24             }
25             res.m[i][j] %= mod;
26         }
27     }
28     return res;
29 }
30 
31 MT Product(MT a, int k)
32 {
33     MT r;
34     memset(r.m, 0, sizeof(r.m));
35     for(int i = 0; i < n; i++)
36     {
37         r.m[i][i] = 1;
38     }
39 
40     while(k)
41     {
42         if(k & 1) r = Mul(r, a);
43         k >>= 1;
44         a = Mul(a, a);
45     }
46     return r;
47 }
48 
49 int main()
50 {
51     MT a;
52     scanf("%d", &t);
53     while(t--)
54     {
55         scanf("%d %d", &n, &k);
56         for(int i = 0; i < n; i++)
57         {
58             for(int j = 0; j < n; j++)
59             {
60                 scanf("%d", &a.m[i][j]);
61             }
62         }
63 
64         MT b = Product(a, k);
65         int ans = 0;
66 
67         for(int i = 0; i < 10; i++)
68         {
69             ans += b.m[i][i]%mod;
70         }
71 
72         printf("%d
", ans % mod);
73     }
74     return 0;
75 }
View Code