NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #204843 | #3630. 数列操作 | lsr | 100 | 8896ms | 11656kb | C++11 | 2.0kb | 2024-06-10 09:56:50 | 2024-06-10 12:02:59 |
answer
#include <bits/stdc++.h>
using namespace std;
#define QwQ3301AwA return 0
#define ll long long
const int N = 105;
const int M = 1e6 + 5;
const int mod = 1e9 + 7;
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int n, m, q;
struct Mat {
int w[N][N];
Mat () {
memset(w, 0, sizeof(w));
}
Mat operator * (const Mat rhs) const {
Mat ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
add(ans.w[i][j], 1ll * w[i][k] * rhs.w[k][j] % mod);
}
}
}
return ans;
}
};
bool op[M];
int x[M], y[M];
Mat g, f;
Mat pw[30];
Mat mul(Mat f, Mat g) {
Mat ans;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
add(ans.w[0][j], 1ll * f.w[0][k] * g.w[k][j] % mod);
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
string s;
cin >> s >> x[i] >> y[i];
x[i]--, y[i]--;
if (s[0] == 's') op[i] = 0;
else op[i] = 1;
}
for (int i = 0; i < n; i++) {
g.w[i][i] = 1;
for (int j = 1; j <= m; j++) {
if (op[j] == 0) swap(g.w[i][x[j]], g.w[i][y[j]]);
else add(g.w[i][x[j]], g.w[i][y[j]]);
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << g.w[i][j] << ' ';
// }
// cout << '\n';
// }
pw[0] = g;
for (int i = 1; i < 30; i++) pw[i] = pw[i - 1] * pw[i - 1];
while (q--) {
for (int i = 0; i < n; i++) cin >> f.w[0][i];
int k;
cin >> k;
for (int i = 0; i < 30; i++) {
if ((k >> i) & 1) f = mul(f, pw[i]);
}
for (int i = 0; i < n; i++) cout << f.w[0][i] << ' ';
cout << '\n';
}
QwQ3301AwA;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 5ms
memory: 2872kb
input:
30 30 30 add 11 7 add 8 26 swap 19 6 add 21 13 swap 28 16 swap 11 18 add 26 14 swap 14 8 swap 11 24 ...
output:
550095038 92418381 507176887 906163279 313105934 570651164 285313314 517015518 438637289 250415289 6...
result:
ok 30 lines
Test #2:
score: 10
Accepted
time: 4ms
memory: 2872kb
input:
30 30 30 swap 5 5 swap 21 3 add 17 1 swap 11 23 add 9 29 add 23 1 add 23 3 swap 23 21 add 3 21 swap ...
output:
287688536 772489543 549962788 868362009 689988914 853729914 20144151 714205769 402286427 810161567 4...
result:
ok 30 lines
Test #3:
score: 10
Accepted
time: 115ms
memory: 2868kb
input:
100 100 100 swap 6 80 swap 88 53 swap 55 59 swap 45 81 swap 4 56 swap 69 85 swap 71 93 swap 97 58 sw...
output:
749336717 24709802 840318246 634954155 259909581 258599455 649551653 296218244 72544480 896050158 31...
result:
ok 100 lines
Test #4:
score: 10
Accepted
time: 120ms
memory: 2872kb
input:
100 100 100 swap 50 26 swap 42 30 swap 43 14 swap 88 24 swap 33 75 swap 84 39 swap 28 46 swap 11 33 ...
output:
772590331 74462880 377435932 687433410 392067538 166828233 215084806 318363631 161238800 327773751 3...
result:
ok 100 lines
Test #5:
score: 10
Accepted
time: 1325ms
memory: 11648kb
input:
100 1000000 1 add 61 62 swap 33 93 swap 86 6 swap 72 16 add 11 94 swap 39 47 swap 41 49 swap 19 6 ad...
output:
346253799 771126444 971288221 851217895 505808154 221609458 688027614 70353229 288594725 941298229 4...
result:
ok single line: '346253799 771126444 971288221 ...4 52682545 701646733 382173771 '
Test #6:
score: 10
Accepted
time: 1617ms
memory: 11652kb
input:
100 1000000 1 add 5 7 swap 87 70 add 74 61 swap 12 64 add 44 9 add 54 6 swap 86 97 swap 28 85 swap 5...
output:
450803790 667372094 419301609 389943582 752771140 804124829 585325182 72383423 966194784 233403679 3...
result:
ok single line: '450803790 667372094 419301609 ... 713392549 328208981 322568321 '
Test #7:
score: 10
Accepted
time: 1272ms
memory: 11648kb
input:
100 1000000 1 add 46 61 add 45 43 swap 62 17 swap 52 8 swap 74 33 swap 76 56 add 35 38 swap 37 69 ad...
output:
125149011 756465812 161024297 688771858 867501504 650402763 595197506 873222233 587955871 81643619 3...
result:
ok single line: '125149011 756465812 161024297 ...2 91971529 757776826 634397245 '
Test #8:
score: 10
Accepted
time: 1468ms
memory: 11652kb
input:
100 1000000 100 swap 91 58 swap 100 84 swap 15 59 swap 50 98 add 5 45 add 24 15 swap 37 2 add 2 55 s...
output:
977736656 530446270 797215529 884989997 700839061 290600516 76651241 425687312 559634624 35286388 41...
result:
ok 100 lines
Test #9:
score: 10
Accepted
time: 1443ms
memory: 11656kb
input:
100 1000000 100 swap 43 7 add 49 61 add 3 18 swap 90 50 add 34 72 swap 47 73 swap 86 51 swap 12 38 a...
output:
883102546 725800572 971218181 922364443 269815718 329364304 159331295 428667708 3431691 503434529 15...
result:
ok 100 lines
Test #10:
score: 10
Accepted
time: 1527ms
memory: 11652kb
input:
100 1000000 100 swap 84 65 add 3 34 swap 91 74 swap 33 94 swap 80 83 swap 69 27 swap 27 99 swap 21 1...
output:
147983174 81716446 161911525 667483078 170580251 709287671 728191563 271802648 733606284 754329389 8...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed
