比赛 |
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;
}