比赛 |
2025.6.7 |
评测结果 |
AAAAAATTTT |
题目名称 |
矩阵幂之和 |
最终得分 |
60 |
用户昵称 |
健康铀 |
运行时间 |
11.914 s |
代码语言 |
C++ |
内存使用 |
5.83 MiB |
提交时间 |
2025-06-07 11:36:28 |
显示代码纯文本
#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() {
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;
}