P3390 【模板】矩阵快速幂

P3390 【模板】矩阵快速幂

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 105, mod = 1e9+7;
 5 ll n, k;
 6 struct MAT {
 7     ll a[maxn][maxn];
 8     MAT(){ memset(a,0,sizeof(a)); }
 9     MAT operator*(MAT p) {
10         MAT res;
11         for (int i = 0; i < n; i++)
12             for (int j = 0; j < n; j++)
13                 for(int k = 0; k < n; k++)
14                     res.a[i][j] = (res.a[i][j]+a[i][k]*p.a[k][j])%mod;
15         return res;
16     }
17 };
18 MAT mat_qpow(MAT A, ll b) {
19     MAT res;
20     for (int i = 0; i < n; i++)
21         res.a[i][i] = 1;
22     while(b) {
23         if(b&1) res = res*A;
24         A = A*A;
25         b >>= 1;
26     }
27     return res;
28 }
29
30 int main() {
31     scanf("%lld%lld",&n,&k);
32     MAT A, ans;
33     for (int i = 0; i < n; i++) {
34         for (int j = 0; j < n; j++) {
35             scanf("%lld",&A.a[i][j]);
36         }
37     }
38     ans = mat_qpow(A,k);
39     for (int i = 0; i < n; i++) {
40         printf("%lld",ans.a[i][0]);
41         for (int j = 1; j < n; j++) {
42             printf(" %lld",ans.a[i][j]);
43         }
44         putchar('\n');
45     }
46     return 0;
47 }