hdu1575 Tr A---矩阵快速幂模板题

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1575

题目大意：

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

解题思路：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 100 + 10;
 4 const int MOD = 9973;
 5 struct Mat
 6 {
 7     int a[maxn][maxn];
 8     int n, m;//n为行数，m为列数
 9     Mat(int n, int m):n(n), m(m)
10     {
11         memset(a, 0, sizeof(a));
12     }
13     void init()
14     {
15         for(int i = 0; i < n; i++)a[i][i] = 1;//初始化成单位矩阵
16     }
17     void output()
18     {
19         for(int i = 0; i < n; i++)
20         {
21             for(int j = 0; j < m; j++)
22             {
23                 cout<<a[i][j]<<" ";
24             }
25             cout<<endl;
26         }
27     }
28 };
29 Mat mul(Mat a, Mat b)//矩阵乘法
30 {
31     Mat tmp(a.n, b.m);//矩阵乘法结果矩阵行数为a的行数，列数为b的列数
32     for(int i = 0; i < a.n; i++)
33     {
34         for(int j = 0; j < b.m; j++)
35         {
36             for(int k = 0; k < a.m; k++)//a.m == b.n(乘法的前提条件)
37             {
38                 tmp.a[i][j] += (a.a[i][k] * b.a[k][j] % MOD);
39                 tmp.a[i][j] %= MOD;
40             }
41         }
42     }
43     return tmp;
44 }
45 Mat pow(Mat a, int n)
46 {
47     Mat tmp(a.n, a.m);
48     tmp.init();
49     while(n)
50     {
51         if(n & 1)tmp = mul(tmp, a);
52         n /= 2;
53         a = mul(a, a);
54     }
55     return tmp;
56 }
57 int main()
58 {
59     int T, n, k;
60     cin >> T;
61     while(T--)
62     {
63         cin >> n >> k;
64         Mat a(n, n);
65         for(int i = 0; i < n; i++)
66         {
67             for(int j = 0; j < n; j++)
68                 cin >> a.a[i][j];
69         }
70         a = pow(a, k);
71         int ans = 0;
72         for(int i = 0; i < n; i++)ans = (ans + a.a[i][i]) % MOD;
73         ans %= MOD;
74         cout<<ans<<endl;
75     }
76 }