记录编号	601272	评测结果	AAAAAAAAAA
题目名称	2481.[HZOI 2016][POJ3233]矩阵幂之和	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	11.934 s
提交时间	2025-06-07 14:56:31	内存使用	5.80 MiB

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

typedef long long ll;

int n;
struct M {
    ll m[30][30];
    M() {
        memset(m, 0, sizeof(m));
    }
};

M b;
ll md;

ll mm(ll a, ll b, ll m) {
    a %= m;
    b %= m;
    ll r = 0;
    while (b) {
        if (b & 1) {
            r = (r + a) % m;
        }
        a = (a + a) % m;
        b >>= 1;
    }
    return r;
}

M ma(M A, M B, ll m) {
    M r;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            r.m[i][j] = (A.m[i][j] + B.m[i][j]) % m;
        }
    }
    return r;
}

M mmul(M A, M B, ll m) {
    M r;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < n; k++) {
            if (A.m[i][k] == 0) continue;
            for (int j = 0; j < n; ++j) {
                ll p = mm(A.m[i][k], B.m[k][j], m);
                r.m[i][j] = (r.m[i][j] + p) % m;
            }
        }
    }
    return r;
}

pair<M, M> sol(ll t, ll m) {
    if (t == 1) {
        return make_pair(b, b);
    }
    if (t % 2 == 0) {
        auto l = sol(t / 2, m);
        M sl = l.first;
        M pl = l.second;
        M pt = mmul(pl, pl, m);
        M rs = mmul(pl, sl, m);
        M st = ma(sl, rs, m);
        return make_pair(st, pt);
    } else {
        auto l = sol(t - 1, m);
        M sl = l.first;
        M pl = l.second;
        M pt = mmul(pl, b, m);
        M st = ma(sl, pt, m);
        return make_pair(st, pt);
    }
}

int main() {
	   ios_base::sync_with_stdio(false);
	    cin.tie(0);
    freopen("matrix_sum.in", "r", stdin);
    freopen("matrix_sum.out", "w", stdout);
    ll k, m_val;
    cin >> n >> k >> m_val;
    md = m_val;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> b.m[i][j];
        }
    }
    auto res = sol(k, m_val);
    M s = res.first;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << s.m[i][j];
            if (j < n - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}