比赛 2025.6.7 评测结果 AAAAAAWWWW
题目名称 矩阵幂之和 最终得分 60
用户昵称 wdsjl 运行时间 0.530 s
代码语言 C++ 内存使用 3.91 MiB
提交时间 2025-06-07 10:30:08
显示代码纯文本
#include <iostream>
#include <cstring>
#define int long long
using namespace std;

const int MAXN = 60;

struct Matrix {
    int data[MAXN][MAXN];
    void init() {
        memset(data, 0, sizeof(data));
        for (int i = 0; i < MAXN; ++i) data[i][i] = 1;
    }
};

Matrix multiply(const Matrix& a, const Matrix& b, int n, int mod) {
    Matrix res;
    memset(res.data, 0, sizeof(res.data));
    for (int i = 0; i < 2*n; ++i) {
        for (int k = 0; k < 2*n; ++k) {
            if (a.data[i][k] == 0) continue;
            for (int j = 0; j < 2*n; ++j) {
                res.data[i][j] = (res.data[i][j] + a.data[i][k] * b.data[k][j]) % mod;
            }
        }
    }
    return res;
}

Matrix matrix_pow(Matrix base, int power, int n, int mod) {
    Matrix res;
    res.init();
    while (power > 0) {
        if (power % 2 == 1) res = multiply(res, base, n, mod);
        base = multiply(base, base, n, mod);
        power /= 2;
    }
    return res;
}

signed main() {
	freopen("matrix_sum.in","r",stdin);
	freopen("matrix_sum.out","w",stdout); 
    int n, k, m;
    cin >> n >> k >> m;
    
    int A[MAXN][MAXN] = {0};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> A[i][j];
    
    Matrix T;
    memset(T.data, 0, sizeof(T.data));
    for (int i = 0; i < n; ++i) {
        T.data[i][i] = 1;
        T.data[i][i + n] = 1;
    }
    for (int i = 0; i < n; ++i)     
        for (int j = 0; j < n; ++j)
            T.data[i + n][j + n] = A[i][j] % m;
    
    Matrix T_k = matrix_pow(T, k, n, m);
    
    Matrix C;
    memset(C.data, 0, sizeof(C.data));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            C.data[i + n][j] = A[i][j] % m;
    
    Matrix result = multiply(T_k, C, n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cout << result.data[i][j] << " ";
        cout << endl;
    }
    return 0;
}