题解 | #矩阵幂#

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > multiMatrix(const vector<vector<int>>& a,
                                 const vector<vector<int>>& b) {
    //a是n*m的,b是m*t的，结果是n*t的
    int n = a.size(), m = a[0].size(),
        t = b[0].size();
    vector<vector<int>> res(n, vector<int>(t, 0));
    for (int i = 0; i < n; i++)//结果的行
        for (int j = 0; j < t; j++)//结果的列
            for (int k = 0; k < m; k++) {//a的列
                res[i][j] += (a[i][k] * b[k][j]);
            }
    return res;
}
vector<vector<int>> powMatrix(const vector<vector<int>>& a, int k) {
    int n = a.size();
    vector<vector<int>> res(n, vector<int>(n, 0));
    // 初始化为单位矩阵
    for (int i = 0; i < n; i++) {
        res[i][i] = 1;
    }
  
    vector<vector<int>> base = a;
    while (k > 0) {
        if (k % 2 == 1) {
            res = multiMatrix(res, base);
        }
        base = multiMatrix(base, base);
        k /= 2;//去掉最后一位
    }
    return res;
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> a(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> a[i][j];
        vector<vector<int>> res = powMatrix(a, k);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (j == n - 1)
                    cout << res[i][j] << endl;
                else
                    cout << res[i][j] << " ";
            }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")