题解 | 矩阵幂 矩阵快速幂

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>

using namespace std;

const int maxn = 10;
struct Matrix {
    int row, col;
    int matrix[maxn][maxn];
    Matrix() {};
    Matrix(int r, int c) : row(r), col(c) {}
};
Matrix multuply(Matrix x, Matrix y) {
    Matrix answer = Matrix(x.row, y.col);
    for (int i = 0; i < x.row; i++) {
        for (int j = 0; j < y.col; j++) {
            answer.matrix[i][j] = 0;
            for (int k = 0; k < x.col; k++) {
                answer.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
            }
        }
    }
    return answer;
}
void printmatrix(Matrix answer) {
    for (int i = 0; i < answer.row; i++) {
        for (int j = 0; j < answer.col; j++) {
            if(j!=0){
                printf(" ");//每行最后一个数后面不应该有多余的空格
            }
            printf("%d", answer.matrix[i][j]);
        }
        printf("\n");
    }
}

Matrix fastexp(Matrix x, int k) {
    Matrix answer(x.row, x.col);
    for (int i = 0; i < x.row; i++) {
        for (int j = 0; j < x.col; j++) {
            if (i == j) {
                answer.matrix[i][j] = 1;

            } else {
                answer.matrix[i][j] = 0;
            }
        }
    }          //类比 int answer =1;
    while (k != 0) {
        if (k % 2 == 1) {
            //answer*=x.matrix;
            answer = multuply(answer, x);
        }
        k /= 2;
        x = multuply(x, x);
    }
    return answer;

}

int main() {
    
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        Matrix x(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <n; j++) {
                scanf("%d", &x.matrix[i][j]);
            }
           
        }
         Matrix answer =fastexp(x,  k);
         printmatrix( answer);

    }
    return 0;
}