题解 | #矩阵幂#

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
struct Matrix {
    int row, col;
    int matrix[MAXN][MAXN];
    Matrix(int x, int y): row(x), col(y) {}
};

Matrix add_matrix(Matrix x, Matrix y) {
    Matrix ansever = Matrix(x.row, x.col);
    for (int i = 0; i < ansever.row; i++) {
        for (int j = 0; j < ansever.col; j++) {
            ansever.matrix[i][j] = x.matrix[i][j] + y.matrix[i][j];
        }
    }
    return ansever;
}

Matrix mutiple(Matrix x, Matrix y) {
    Matrix ansever = Matrix(x.row, y.col);
    for (int i = 0; i < ansever.row; i++) {
        for (int j = 0; j < ansever.col; j++) {
            ansever.matrix[i][j] = 0;
            for (int k = 0; k < x.col; k++) {
                ansever.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
            }
        }
    }
    return ansever;
}

Matrix Quickpover(Matrix x, int n) {
    Matrix ansever(x.row, x.col);
    for (int i = 0; i < x.row; i++) { //初始化别忘了,初始化为单位矩阵
        for (int j = 0; j < x.col; j++) {
            if (i == j)ansever.matrix[i][j] = 1;
            else ansever.matrix[i][j] = 0;
        }
    }
    while (n != 0) {
        if (n % 2 == 1) {
            ansever = mutiple(ansever, x);
        }
        n /= 2;
        x = mutiple(x, x);
    }
    return ansever;
}

Matrix Traspose(Matrix x) {
    Matrix ansever(x.row, x.col);
    for (int i = 0; i < x.row; i++) {
        for (int j = 0; j < x.row; j++) {
            ansever.matrix[i][j] = x.matrix[j][i];
        }
    }
    return ansever;
}

void Inputmatrix(Matrix& x) {
    for (int i = 0; i < x.row; i++) {
        for (int j = 0; j < x.col; j++) {
            scanf("%d", &x.matrix[i][j]);
        }
    }
    return;
}
void Outputmatrix(Matrix x) {
    for (int i = 0; i < x.row; i++) {
        for (int j = 0; j < x.col; j++) {
            if (j == 0)printf("%d", x.matrix[i][j]);
            else printf(" %d",
                            x.matrix[i][j]); //每行数之间用空格隔开，注意，每行最后一个数后面不应该有多余的空格。
        }
        cout << endl;
    }
    return;
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        Matrix ansever(n, n);
        Inputmatrix(ansever);
        ansever = Quickpover(ansever, k);
        Outputmatrix(ansever);
    }
    return 0;
}