矩阵快速幂

 1 #include 
 2 #define int long long
 3 using namespace std;
 4 const int N = 105;
 5 const int mod = 1e7 + 9;
 6 int n, k;
 7 struct node {
 8     int c[N][N];
 9 } A, B;
10 node operator*(const node& x, const node& y) {
11     node a;
12     for(int i = 1; i <= n; i++) {
13         for(int j = 1; j <= n; j++) {
14             a.c[i][j] = 0;
15         }
16     }
17     for(int i = 1; i <= n; i++) {
18         for(int j = 1; j <= n; j++) {
19             for(int k = 1; k <= n; k++) {
20                 a.c[i][j] += x.c[i][k] * y.c[k][j] % mod;
21                 a.c[i][j] %= mod;
22             }
23         }
24     }
25     return a;
26 }
27 signed main() {
28     scanf("%d%d", &n, &k);
29     for(int i = 1; i <= n; i++) {
30         for(int j = 1; j <= n; j++) {
31             scanf("%d", &A.c[i][j]);
32         }
33     }
34     for(int i = 1; i <= n; i++) B.c[i][i] = 1;
35     while(k) {
36         if(k & 1) B = B * A;
37         A = A * A;
38         k >>= 1;
39     }
40     for(int i = 1; i <= n; i++) {
41         for(int j = 1; j <= n; j++) {
42             printf("%lld ", B.c[i][j]);
43         }
44         puts("");
45     }
46     return 0;
47 }