NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #203750 | #2595. 争辩 | tkswls | 100 | 8467ms | 411440kb | C++11 | 1.3kb | 2024-03-12 11:28:16 | 2024-03-12 12:45:17 |
answer
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
using namespace std;
const int mod = 998244353;
int n, m, f[5005][5005][2], a[5005][5005], ans, cnt, sum;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> a[1][1] >> a[1][2];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = (a[i - 1][j] + a[i - 1][j - 1] * a[i - 1][j - 1] % mod) % mod;
}
}
ans = a[1][1] + a[1][2];
for (int i = 2; i <= n; i++) {
sum = 0;
for (int j = 1; j <= n; j++) {
sum = (sum + a[i][j]) % mod;
}
ans = (ans * sum) % mod;
}
f[1][1][0] = a[1][2];
f[1][2][0] = a[1][1];
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i + 1; j++) {
f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][1] * a[i + 1][i + 2] % mod) % mod;
f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][0] * a[i + 1][i + 2] % mod) % mod;
f[i + 1][i + 2][1] = (f[i + 1][i + 2][1] + f[i][j][1 ^ ((i - j + 1) & 1)] * a[i + 1][j] % mod) % mod;
f[i + 1][i + 2][0] = (f[i + 1][i + 2][0] + f[i][j][(i - j + 1) & 1] * a[i + 1][j] % mod) % mod;
}
}
cnt = f[n][n + 1][1];
cout << (ans - cnt + mod) % mod << " " << cnt << "\n";
}
//好好好，题目做法与生成方式强相关
//A 题只会40pts
//C 啥也不会，信仰剪枝可以拿到30pts
详细
小提示：点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1288kb
input:
5 744218482 587881324
output:
13138450 674513789
result:
ok 2 number(s): "13138450 674513789"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1308kb
input:
7 375298450 758982401
output:
115891835 511945258
result:
ok 2 number(s): "115891835 511945258"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
7 747662898 29322575
output:
763506111 480999896
result:
ok 2 number(s): "763506111 480999896"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1292kb
input:
5 17995117 557947449
output:
355859117 865101432
result:
ok 2 number(s): "355859117 865101432"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
7 605627710 283651592
output:
971512951 11772776
result:
ok 2 number(s): "971512951 11772776"
Test #6:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
7 439376093 122637152
output:
902262398 459529853
result:
ok 2 number(s): "902262398 459529853"
Test #7:
score: 0
Accepted
time: 0ms
memory: 1296kb
input:
6 294443169 355430699
output:
857087887 575785897
result:
ok 2 number(s): "857087887 575785897"
Test #8:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
5 144446007 959773782
output:
968965005 899011360
result:
ok 2 number(s): "968965005 899011360"
Test #9:
score: 0
Accepted
time: 0ms
memory: 1292kb
input:
5 372515971 231400104
output:
208587635 882119902
result:
ok 2 number(s): "208587635 882119902"
Test #10:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
5 363180872 50638386
output:
22385294 589015244
result:
ok 2 number(s): "22385294 589015244"
Subtask #2:
score: 40
Accepted
Test #11:
score: 40
Accepted
time: 0ms
memory: 1400kb
input:
18 402208694 142404782
output:
664542090 318440879
result:
ok 2 number(s): "664542090 318440879"
Test #12:
score: 0
Accepted
time: 0ms
memory: 1420kb
input:
20 788226473 652105198
output:
280068226 90446507
result:
ok 2 number(s): "280068226 90446507"
Test #13:
score: 0
Accepted
time: 0ms
memory: 1408kb
input:
19 414216178 827086324
output:
457052879 178556662
result:
ok 2 number(s): "457052879 178556662"
Test #14:
score: 0
Accepted
time: 0ms
memory: 1416kb
input:
20 737491619 250713190
output:
320228222 37198101
result:
ok 2 number(s): "320228222 37198101"
Test #15:
score: 0
Accepted
time: 0ms
memory: 1408kb
input:
19 593753735 976033837
output:
771734088 674509363
result:
ok 2 number(s): "771734088 674509363"
Test #16:
score: 0
Accepted
time: 0ms
memory: 1420kb
input:
20 862335898 477060005
output:
1197379 704271660
result:
ok 2 number(s): "1197379 704271660"
Test #17:
score: 0
Accepted
time: 0ms
memory: 1400kb
input:
18 778567205 87766799
output:
131960945 633854544
result:
ok 2 number(s): "131960945 633854544"
Test #18:
score: 0
Accepted
time: 0ms
memory: 1404kb
input:
18 164205692 899125348
output:
766828820 93666400
result:
ok 2 number(s): "766828820 93666400"
Test #19:
score: 0
Accepted
time: 0ms
memory: 1412kb
input:
19 750486821 621630820
output:
879985755 703270635
result:
ok 2 number(s): "879985755 703270635"
Test #20:
score: 0
Accepted
time: 0ms
memory: 1412kb
input:
19 376388967 24955412
output:
238035491 426626334
result:
ok 2 number(s): "238035491 426626334"
Subtask #3:
score: 20
Accepted
Test #21:
score: 20
Accepted
time: 449ms
memory: 408976kb
input:
4978 910514213 0
output:
788089228 0
result:
ok 2 number(s): "788089228 0"
Test #22:
score: 0
Accepted
time: 290ms
memory: 409440kb
input:
4982 429341599 0
output:
172299293 0
result:
ok 2 number(s): "172299293 0"
Test #23:
score: 0
Accepted
time: 361ms
memory: 406632kb
input:
4958 425961947 0
output:
990581912 0
result:
ok 2 number(s): "990581912 0"
Test #24:
score: 0
Accepted
time: 473ms
memory: 411440kb
input:
4999 197448521 0
output:
941601601 0
result:
ok 2 number(s): "941601601 0"
Test #25:
score: 0
Accepted
time: 468ms
memory: 411440kb
input:
4999 960597363 0
output:
914649065 0
result:
ok 2 number(s): "914649065 0"
Test #26:
score: 0
Accepted
time: 515ms
memory: 406508kb
input:
4957 677708123 0
output:
11518657 0
result:
ok 2 number(s): "11518657 0"
Test #27:
score: 0
Accepted
time: 409ms
memory: 410148kb
input:
4988 538608731 0
output:
86612867 0
result:
ok 2 number(s): "86612867 0"
Test #28:
score: 0
Accepted
time: 337ms
memory: 406864kb
input:
4960 459034697 0
output:
992590866 0
result:
ok 2 number(s): "992590866 0"
Test #29:
score: 0
Accepted
time: 386ms
memory: 411200kb
input:
4997 219194873 0
output:
270936189 0
result:
ok 2 number(s): "270936189 0"
Test #30:
score: 0
Accepted
time: 477ms
memory: 407216kb
input:
4963 366226942 0
output:
620445697 0
result:
ok 2 number(s): "620445697 0"
Subtask #4:
score: 20
Accepted
Test #31:
score: 20
Accepted
time: 511ms
memory: 406156kb
input:
4954 691383869 208580550
output:
704544576 10280802
result:
ok 2 number(s): "704544576 10280802"
Test #32:
score: 0
Accepted
time: 457ms
memory: 405920kb
input:
4952 857975980 826442723
output:
214389172 475475570
result:
ok 2 number(s): "214389172 475475570"
Test #33:
score: 0
Accepted
time: 351ms
memory: 409676kb
input:
4984 735861554 929244545
output:
887999971 312795892
result:
ok 2 number(s): "887999971 312795892"
Test #34:
score: 0
Accepted
time: 452ms
memory: 410384kb
input:
4990 303201371 687344074
output:
675281990 631594314
result:
ok 2 number(s): "675281990 631594314"
Test #35:
score: 0
Accepted
time: 521ms
memory: 409088kb
input:
4979 317407558 814706802
output:
317645643 231966120
result:
ok 2 number(s): "317645643 231966120"
Test #36:
score: 0
Accepted
time: 520ms
memory: 409324kb
input:
4981 128509607 50340227
output:
355910319 781926266
result:
ok 2 number(s): "355910319 781926266"
Test #37:
score: 0
Accepted
time: 447ms
memory: 409444kb
input:
4982 918721664 582688638
output:
533986199 763920958
result:
ok 2 number(s): "533986199 763920958"
Test #38:
score: 0
Accepted
time: 375ms
memory: 408388kb
input:
4973 458320641 749155979
output:
197623718 395556020
result:
ok 2 number(s): "197623718 395556020"
Test #39:
score: 0
Accepted
time: 338ms
memory: 406632kb
input:
4958 133389904 50372735
output:
901400891 79732175
result:
ok 2 number(s): "901400891 79732175"
Test #40:
score: 0
Accepted
time: 330ms
memory: 405920kb
input:
4952 334593776 497500113
output:
238094340 21721809
result:
ok 2 number(s): "238094340 21721809"
Extra Test:
score: 0
Extra Test Passed
