不使用快速幂的标准方法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll k;
    cin >> n >> k;

    // 读入原矩阵 A，注意取模并处理可能的负数
    vector<vector<ll>> A(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ll x;
            cin >> x;
            // 统一转为 [0, MOD) 范围内
            A[i][j] = (x % MOD + MOD) % MOD;
        }
    }

    // 如果 k == 0，A^0 定义为单位矩阵 I
    vector<vector<ll>> result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        result[i][i] = 1;
    }

    // 普通矩阵乘法重复 k 次，得到 A^k
    // 每一次： result = result * A
    vector<vector<ll>> tmp(n, vector<ll>(n));
    for (ll step = 0; step < k; step++) {
        // 清空 tmp，用于存放这一次的乘积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i][j] = 0;
            }
        }
        // 三重循环完成矩阵乘法
        // tmp[i][j] = sum_{l=0..n-1} result[i][l] * A[l][j]
        for (int i = 0; i < n; i++) {
            for (int l = 0; l < n; l++) {
                if (result[i][l] == 0) continue;  // 小优化：跳过零元素
                ll v = result[i][l];
                for (int j = 0; j < n; j++) {
                    tmp[i][j] = (tmp[i][j] + v * A[l][j]) % MOD;
                }
            }
        }
        // 将 tmp 复制回 result，为下一轮做准备
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = tmp[i][j];
            }
        }
    }

    // 输出结果矩阵 result，即 A^k mod 10^9+7
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << result[i][j] << (j + 1 == n ? '\n' : ' ');
        }
    }

    return 0;
}

矩阵快速幂自己方法：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;  // 模数 10^9+7

// 动态数组矩阵类型，大小 n×n
using mat = vector<vector<ll>>;

/// 矩阵乘法：返回 C = A * B （均为 n×n 矩阵）
/// 时间复杂度 O(n^3)
mat mmul(const mat &A, const mat &B) {
    int n = A.size();
    mat C(n, vector<ll>(n, 0));  // 动态分配结果矩阵并初始化为 0
    // 三层循环实现：按行×列
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            ll v = A[i][k];
            if (v == 0) continue;  // 跳过 0 可以加速
            for (int j = 0; j < n; j++) {
                // C[i][j] += A[i][k] * B[k][j]，并取模防止溢出
                C[i][j] = (C[i][j] + v * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

/// 快速矩阵幂：返回 A^e （n×n 矩阵）
/// 核心：二进制快速幂，把指数 e 拆成二进制位
mat mpow(mat A, ll e) {
    int n = A.size();
    // 初始化结果为单位矩阵 I_n
    mat R(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        R[i][i] = 1;
    }
    // 当 e > 0 时循环
    while (e > 0) {
        if (e & 1) {
            // 当前位为 1，就用 R = R * A
            R = mmul(R, A);
        }
        // A 自身平方：A = A * A
        A = mmul(A, A);
        // 处理下一位
        e >>= 1;
    }
    return R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll k;
    cin >> n >> k;
    // 读入原矩阵 A，使用动态数组（vector）存储
    mat A(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> A[i][j];
            // 取模并处理负数
            A[i][j] %= MOD;
            if (A[i][j] < 0) A[i][j] += MOD;
        }
    }

    // 计算 A^k
    mat B = mpow(A, k);

    // 输出结果矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << B[i][j] << (j + 1 < n ? ' ' : '\n');
        }
    }
    return 0;
}