题解 | #矩阵幂#

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 10;
struct Matrix {
    int row, col;
    int matrix[MAXN][MAXN];
    Matrix(int r, int c) :row(r), col(c) {}
};
Matrix Multiply(Matrix x, Matrix y) {
    Matrix ans = Matrix(x.row, y.col);
    for (int i = 0; i < ans.row; ++i) {
        for (int j = 0; j < ans.col; ++j) {
            ans.matrix[i][j] = 0;
            for (int k = 0; k < x.col; ++k) {
                ans.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
            }
        }
    }
    return ans;
}
 
void CoutMatrix(Matrix x) {
    for (int i = 0; i < x.row; ++i) {
        for (int j = 0; j < x.col; ++j) {
            if (j) {
                printf(" ");
            }
            printf("%d", x.matrix[i][j]);
        }
        printf("\n");
    }
}
Matrix QuickPower(Matrix x, int k) {
    Matrix ans = Matrix(x.row, x.col);
    for (int i = 0; i < ans.row; ++i) {
        for (int j = 0; j < ans.col; ++j) {
            ans.matrix[i][j] = i == j ? 1 : 0;
        }
    }
    while (k) {
        if (k % 2) {
            ans = Multiply(ans, x);
        }
        k /= 2;
        x = Multiply(x, x);
    }
    return ans;
}
int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        Matrix x = Matrix(n, n);
        for (int i = 0; i < x.row; ++i) {
            for (int j = 0; j < x.col; ++j) {
                scanf("%d", &x.matrix[i][j]);
            }
        }
        CoutMatrix(QuickPower(x, k));
    }
    return 0;
}