1 条题解
-
0
【本题解由站长编写】
矩阵快速幂没必要,M≤5 直接模拟乘方:先准备单位矩阵应对 M=0,然后把 A 自乘 M 次。元素最大约 10⁵×30⁴,要用 long long。
代码(C++17)
#include <bits/stdc++.h> using namespace std; typedef vector<vector<long long>> Mtx; Mtx mul(const Mtx &a, const Mtx &b) { int n = a.size(); Mtx c(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) for (int k = 0; k < n; k++) for (int j = 0; j < n; j++) c[i][j] += a[i][k] * b[k][j]; return c; } int main() { int n; long long m; cin >> n >> m; Mtx a(n, vector<long long>(n)); for (auto &r : a) for (auto &x : r) cin >> x; Mtx r(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) r[i][i] = 1; for (long long i = 0; i < m; i++) r = mul(r, a); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cout << r[i][j] << (j + 1 == n ? "\n" : " "); return 0; }
- 1
信息
- ID
- 4083
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者