题解 | #矩阵幂#

#include <iostream>
#include <cstdio>
// 矩阵快速幂：求方阵的幂

using namespace std;

struct Matrix { //定义矩阵结构体
    int mtrx[10][10]; // 数组的shape应该初始化为多少需要根据题目或者时间确定，不能太小，否则程序运行报错
    int row;
    int col;
    Matrix(int r, int c) : row(r), col(c) {} // 构造函数
};

Matrix matrixMlutiply(Matrix x, Matrix y) { // 矩阵乘法函数
    Matrix answer(x.row, y.col);
    for (int i = 0; i < x.row; ++i) {
        for (int j = 0; j < y.col; ++j) {
            answer.mtrx[i][j] = 0;
            for (int k = 0; k < x.col; ++k) {
                answer.mtrx[i][j] += x.mtrx[i][k] * y.mtrx[k][j];
            }
        }
    }
    return answer;
}

void printMatrix(Matrix x) { // 矩阵打印函数
    for (int i = 0; i < x.row; ++i) {
        for (int j = 0; j < x.col; ++j) {
            if (j == 0) {
                printf("%d", x.mtrx[i][j]);
            } else {
                printf(" %d", x.mtrx[i][j]);
            }
        }
        printf("\n");
    }
    return;
};


Matrix matrixFastExp(Matrix x, int k) { // 矩阵快速幂函数
    Matrix answer(x.row, x.col);
    for (int i = 0; i < x.row; ++i) { //初始化为单位阵
        for (int j = 0; j < x.row; ++j) {
            if (i == j) {
                answer.mtrx[i][j] = 1;
            } else {
                answer.mtrx[i][j] = 0;
            }
        }
    }
    while (k != 0) {
        if (k % 2 == 1 ) {
            answer = matrixMlutiply(answer, x);
        }
        x = matrixMlutiply(x, x);
        k /= 2;
    }
    return answer;
};


int main() {
    int n, k;
    while (scanf("%d%d", &n,
                 &k) != EOF) { // 注意：输入多个数字时不需要用空格指代
        Matrix x(n, n);
        for (int i = 0; i < x.row; ++i) {
            for (int j = 0; j < x.col; ++j) {
                scanf("%d", &x.mtrx[i][j]);
            }
        }
        Matrix res = matrixFastExp(x, k);
        printMatrix(res);
    }
    return 0;
}