题解 | #矩阵幂#

#include <iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
struct Matrix {
    int row, col;
    int matrix[10][10];
    Matrix(int r, int c): row(r), col(c) {}
};
void printMatrix(Matrix res) {
    for (int i = 0; i < res.row; i++) {
        for (int j = 0; j < res.col; j++) {
            cout << res.matrix[i][j] << " ";

        }
        cout << "\n";
    }
}
Matrix multiMatrix(Matrix A, Matrix B) {
    Matrix res(A.row, B.col);
    for (int i = 0; i < A.row; i++) {
        for (int j = 0; j < B.col; j++) {
            res.matrix[i][j] = 0;
            for (int k = 0; k < A.col; k++) {
                res.matrix[i][j] += A.matrix[i][k] * B.matrix[k][j];
            }
        }
    }
    return res;
}
//求k次幂
Matrix matricExp(Matrix A, int k) {
    Matrix res(A.row, A.col);
    for (int i = 0; i < A.row; i++) {
        for (int j = 0; j < A.col; j++) {
            if (i == j) {
                res.matrix[i][j] = 1;
            } else {
                res.matrix[i][j] = 0;
            }
        }
    }
    while (k != 0) {
        if (k % 2 == 1) { //如果最后一位为1
            res = multiMatrix(res, A);
        }
        A = multiMatrix(A, A); //下一次循环时，最后一位的权值
        k /= 2;
//      cout<<"当前矩阵为\n";
//      printMatrix(res);
    }
    return res;
}
int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        Matrix A(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &A.matrix[i][j]);
//                cout<<"test1:"<<A.matrix[i][j]<<" "<<"\n";
            }
        }
//        printMatrix(A);
        Matrix answer = matricExp(A, k);
        printMatrix(answer);
    }
    return 0;
}