今天我刷题了吗
搜索文档…
矩阵快速幂
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int mod(1e9 + 7);
7
const int maxn(1e2 + 10);
8
9
template<typename T = int>
10
inline const T read()
11
{
12
T x = 0, f = 1;
13
char ch = getchar();
14
while (ch < '0' or ch > '9') {
15
if (ch == '-') f = -1;
16
ch = getchar();
17
}
18
while (ch >= '0' and ch <= '9') {
19
x = (x << 3) + (x << 1) + ch - '0';
20
ch = getchar();
21
}
22
return x * f;
23
}
24
25
template<typename T>
26
inline void write(T x, char c)
27
{
28
if (x < 0) {
29
putchar('-');
30
x = -x;
31
}
32
if (x > 9) write(x / 10, false);
33
putchar(x % 10 + '0');
34
if (c) putchar(c);
35
}
36
37
struct matrix {
38
int n;
39
ll val[maxn][maxn];
40
41
matrix(vector<vector<int>> vec)
42
{
43
assert(vec.size() == vec.front().size());
44
this->n = (int)vec.size();
45
for (int i = 0; i < n; ++i) {
46
for (int j = 0; j < n; ++j) {
47
val[i][j] = vec[i][j];
48
}
49
}
50
}
51
52
matrix(int n, bool id = false)
53
{
54
this->n = n;
55
memset(val, 0, sizeof val);
56
if (not id) return;
57
// identity matrix
58
for (int i = 0; i < n; ++i) {
59
val[i][i] = id;
60
}
61
}
62
63
matrix operator *(const matrix& rhs) {
64
assert(n == rhs.n);
65
matrix res(n);
66
for (int i = 0; i < n; ++i) {
67
for (int j = 0; j < n; ++j) {
68
for (int k = 0; k < n; ++k) {
69
res.val[i][j] = (res.val[i][j] + val[i][k] * rhs.val[k][j] % mod) % mod;
70
}
71
}
72
}
73
return res;
74
};
75
76
matrix operator ^(ll k)
77
{
78
matrix res(n, true), x = *this;
79
while (k) {
80
if (k bitand 1) {
81
res = res * x;
82
}
83
x = x * x;
84
k >>= 1;
85
}
86
return res;
87
}
88
};
89
90
int main()
91
{
92
#ifndef ONLINE_JUDGE
93
freopen("input.txt", "r", stdin);
94
#endif
95
int n = read();
96
ll k = read<ll>();
97
matrix mat(n);
98
for (int i = 0; i < n; ++i) {
99
for (int j = 0; j < n; ++j) {
100
mat.val[i][j] = read();
101
}
102
}
103
mat = mat ^ k;
104
for (int i = 0; i < n; ++i) {
105
for (int j = 0; j < n; ++j) {
106
write(mat.val[i][j], j == n - 1 ? '\n' : ' ');
107
}
108
}
109
return 0;
110
}
Copied!
最近更新 11mo ago
复制链接