hdu 1575 Tr A（矩阵快速幂乘法优化算法）

Problem Description

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

Input

数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

Output

对应每组数据，输出Tr(A^k)%9973。

Sample Input

Sample Output

2 
2686

Author

xhd

Source

HDU 2007-1 Programming Contest

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 10
 6 #define MOD 9973
 7 int n,k;
 8 struct Matrix
 9 {
10     int mp[N][N];
11 }matrix;
12 Matrix Mul(Matrix a,Matrix b)
13 {
14     Matrix res;
15     int i,j,k;
16     for(i=0;i<n;i++)
17     {
18         for(j=0;j<n;j++)
19         {
20             res.mp[i][j] = 0;
21             for(k=0;k<n;k++)
22                 res.mp[i][j] = (res.mp[i][j]+(a.mp[i][k]*b.mp[k][j]))%MOD;
23         }
24     }
25     return res;
26 }
27 
28 Matrix fastm(Matrix a,int b)
29 {
30     Matrix res;
31     memset(res.mp,0,sizeof(res.mp));
32         for(int i=0;i<n;i++)
33             res.mp[i][i] = 1;
34     while(b)
35     {
36         if(b&1)
37             res = Mul(res,a);
38         a = Mul(a,a);
39         b >>= 1;
40     }
41     return res;
42 }
43 int main()
44 {
45     int t;
46     scanf("%d",&t);
47     while(t--)
48     {
49         scanf("%d%d",&n,&k);
50         for(int i=0;i<n;i++)
51         {
52             for(int j=0;j<n;j++)
53             {
54                 scanf("%d",&matrix.mp[i][j]);
55             }
56         }
57         Matrix tmp=fastm(matrix,k);
58         int ans=0;
59         for(int i=0;i<n;i++)
60         {
61             ans=(ans+tmp.mp[i][i])%MOD;
62         }
63         printf("%d
",ans);
64     }
65     return 0;
66 }

View Code