P3390 【模板】矩阵快速幂

#include <bits/stdc++.h>
using namespace std;
const int T = 1e9 + 7;
long long n, k;
struct node {
    long long a[110][110];
    node() { memset(a, 0, sizeof(a)); }
    void build() {
        for (int i = 1; i <= n; i++) a[i][i] = 1;
    }
} b;
node operator*(const node& x, const node& y) {
    node z;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % T) % T;
        }
    return z;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> b.a[i][j];
    node ans;
    ans.build();
    while (k) {
        if (k & 1) ans = ans * b;
        b = b * b;
        k = k >> 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << ans.a[i][j] << " ";
        cout << endl;
    }
}