51nod 1113 矩阵快速幂

模板题，学习下。
 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 101;
 8 const int mod = 1e9+7;
 9 int n, m;
10 struct Mat{//矩阵
11     ll mat[N][N];
12 };
13 Mat operator * (Mat a, Mat b){//一次矩阵乘法
14     Mat c;
15     memset(c.mat, 0, sizeof(c.mat));
16     int i, j, k;
17     for(k = 1; k <= n; ++k){
18         for(i = 1; i <= n; ++i){
19             if(a.mat[i][k] <= 0) continue;
20             for(j = 1; j <= n; ++j){
21                 if(b.mat[k][j] <= 0) continue;
22                 c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
23                 c.mat[i][j] %= mod;
24             }
25         }
26     }
27     return c;
28 }
29 Mat operator ^ (Mat a, int k){//矩阵快速幂，a^k
30     Mat c;
31     int i, j;
32     for(i = 1; i <= n; ++i)
33         for(j = 1; j <= n; ++j)
34             c.mat[i][j] = (i == j);//初始化为单位矩阵
35     while(k){
36         if(k & 1)
37             c = c * a;
38         a = a * a;
39         k >>= 1;
40     }
41     return c;
42 }
43 int main(){
44     scanf("%d%d", &n, &m);
45     int i, j;
46     Mat a;
47     for(i = 1; i <= n; ++i)
48         for(j = 1; j <= n; ++j)
49             scanf("%lld", &a.mat[i][j]);
50     Mat c = a ^ m;
51     for(i = 1; i <= n; ++i){
52         for(j = 1; j < n; ++j)
53             printf("%lld ", c.mat[i][j]);
54         printf("%lld
", c.mat[i][n]);
55     }
56     return 0;
57 }
View Code