P3390

cpp
#include <iostream>
#include <vector>
#include <cstring>

const int MOD = 1000000007;

// 定义一个矩阵结构
struct Matrix {
    int n;  // 矩阵的维度
    std::vector<std::vector<int>> data;  // 矩阵数据

    Matrix(int _n) : n(_n), data(_n, std::vector<int>(_n, 0)) {}

    // 创建并返回一个单位矩阵
    static Matrix identity(int n) {
        Matrix mat(n);
        for (int i = 0; i < n; ++i) {
            mat.data[i][i] = 1;
        }
        return mat;
    }

    // 矩阵相乘操作
    Matrix operator*(const Matrix& other) const {
        Matrix result(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    // 用模运算防止整数溢出
                    result.data[i][j] = (result.data[i][j] + 1LL * data[i][k] * other.data[k][j] % MOD) % MOD;
                }
            }
        }
        return result;
    }
};

// 矩阵的高次幂计算
Matrix matrixPower(Matrix mat, long long k) {
    int n = mat.n;
    Matrix result = Matrix::identity(n);
    while (k) {
        if (k % 2) {
            result = result * mat;
        }
        mat = mat * mat;
        k /= 2;
    }
    return result;
}

int main() {
    int n, k;
    std::cin >> n >> k;
    Matrix A(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> A.data[i][j];
        }
    }

    Matrix result = matrixPower(A, k);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << result.data[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}