ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#949 | #210. 「CSP-S2019」Emiya 家今天的饭 | FiraCode | 100 | 1848ms | 4328kb | C++14 | 1.2kb | 2025-07-05 08:35:21 | 2025-07-05 11:16:45 |
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m;
int a[110][2010];
int f[110][210];
int sum = 0;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]), a[i][0] = (a[i][0] + a[i][j]) % mod;
sum = a[1][0] + 1;
for (int i = 2; i <= n; ++i) sum = 1ll * sum * (a[i][0] + 1) % mod;
f[0][100] = 1;
int res = 0;
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
for (int k = 0; k <= 201; ++k) {
f[i][k] = 0;
}
}
// cout << j << "----" << endl;
int l = 100, r = 100;
for (int i = 1; i <= n; ++i) {
--l, ++r;
for (int k = l; k <= r; ++k) {
f[i][k] = f[i - 1][k];
if (k) f[i][k] += 1ll * f[i - 1][k - 1] * a[i][j] % mod;
if (f[i][k] >= mod) f[i][k] -= mod;
if (k + 1 <= r) f[i][k] += 1ll * f[i - 1][k + 1] * ((a[i][0] - a[i][j] + mod) % mod) % mod;
if (f[i][k] >= mod) f[i][k] -= mod;
// cout << f[i][k] << ' ' << i << ' ' << k << endl;
}
}
for (int k = 101; k <= 201; ++k) {
res += f[n][k];
if (res >= mod) res -= mod;
}
}
// cout << res << ' ' << sum << endl;
printf("%d\n", (sum - res - 1 + mod) % mod);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 4
Accepted
time: 0ms
memory: 3344kb
input:
2 2 1 1 1 1
output:
2
result:
ok "2"
Test #2:
score: 4
Accepted
time: 0ms
memory: 3452kb
input:
2 3 1 1 1 1 0 1
output:
4
result:
ok "4"
Test #3:
score: 4
Accepted
time: 1ms
memory: 3520kb
input:
5 2 1 1 1 0 1 1 1 1 1 1
output:
34
result:
ok "34"
Test #4:
score: 4
Accepted
time: 0ms
memory: 3388kb
input:
5 3 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
output:
358
result:
ok "358"
Test #5:
score: 4
Accepted
time: 0ms
memory: 3500kb
input:
10 2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1
output:
1372
result:
ok "1372"
Test #6:
score: 4
Accepted
time: 1ms
memory: 3320kb
input:
10 3 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1
output:
22211
result:
ok "22211"
Test #7:
score: 4
Accepted
time: 0ms
memory: 3440kb
input:
10 2 470 495 570 77 871 183 513 511 425 250 7 432 132 782 256 487 641 73 914 775
output:
780126716
result:
ok "780126716"
Test #8:
score: 4
Accepted
time: 1ms
memory: 3452kb
input:
10 3 538 604 92 820 608 23 652 172 261 609 153 740 190 464 751 117 726 307 895 785 702 111 967 268 6...
output:
342232854
result:
ok "342232854"
Test #9:
score: 4
Accepted
time: 0ms
memory: 3432kb
input:
40 2 487 641 73 914 775 246 808 99 282 580 620 782 167 690 474 796 808 783 392 519 834 5 972 1 467 6...
output:
951514275
result:
ok "951514275"
Test #10:
score: 4
Accepted
time: 0ms
memory: 3508kb
input:
40 2 538 414 648 613 57 9 287 508 552 559 960 212 715 552 708 893 302 375 906 362 979 541 897 426 89...
output:
502934077
result:
ok "502934077"
Test #11:
score: 4
Accepted
time: 1ms
memory: 3516kb
input:
40 2 595 625 8 446 113 882 348 337 342 655 544 368 643 635 128 757 213 456 495 876 964 997 359 191 8...
output:
153558069
result:
ok "153558069"
Test #12:
score: 4
Accepted
time: 0ms
memory: 3668kb
input:
40 2 596 510 719 843 211 572 801 826 602 261 873 470 646 518 27 730 784 959 902 970 252 177 91 87 27...
output:
808436941
result:
ok "808436941"
Test #13:
score: 4
Accepted
time: 1ms
memory: 3780kb
input:
40 3 117 726 307 895 785 702 111 967 268 629 331 404 10 693 946 57 85 272 697 911 862 290 200 255 67...
output:
383401757
result:
ok "383401757"
Test #14:
score: 4
Accepted
time: 0ms
memory: 3776kb
input:
40 3 232 394 355 698 957 304 761 736 835 773 331 773 273 798 732 749 152 429 61 262 724 292 408 39 7...
output:
876960614
result:
ok "876960614"
Test #15:
score: 4
Accepted
time: 0ms
memory: 3460kb
input:
40 3 112 441 594 869 723 664 464 507 646 496 256 114 53 580 350 538 644 694 130 102 607 240 821 724 ...
output:
607396887
result:
ok "607396887"
Test #16:
score: 4
Accepted
time: 1ms
memory: 3668kb
input:
40 3 72 294 71 147 783 326 970 616 808 85 370 302 920 327 363 54 568 72 634 140 248 87 907 969 80 54...
output:
919724636
result:
ok "919724636"
Test #17:
score: 4
Accepted
time: 21ms
memory: 3524kb
input:
40 500 52 116 373 413 451 955 518 27 696 252 359 888 99 776 798 96 482 713 484 67 392 146 286 572 44...
output:
69641733
result:
ok "69641733"
Test #18:
score: 4
Accepted
time: 19ms
memory: 3560kb
input:
40 500 360 62 703 876 60 896 572 289 805 201 654 742 574 380 492 915 301 377 467 484 991 98 985 538 ...
output:
572832160
result:
ok "572832160"
Test #19:
score: 4
Accepted
time: 21ms
memory: 3560kb
input:
40 500 81 598 214 492 170 225 145 824 830 143 163 710 864 281 93 338 488 469 608 110 238 29 537 761 ...
output:
772057043
result:
ok "772057043"
Test #20:
score: 4
Accepted
time: 19ms
memory: 3796kb
input:
40 500 336 548 143 776 76 916 710 442 250 579 603 407 76 973 492 882 617 368 354 816 977 796 225 144...
output:
73864683
result:
ok "73864683"
Test #21:
score: 4
Accepted
time: 20ms
memory: 3576kb
input:
40 500 330 863 277 27 759 486 461 32 526 332 282 933 467 745 800 451 498 787 678 399 6 691 868 531 4...
output:
293354841
result:
ok "293354841"
Test #22:
score: 4
Accepted
time: 422ms
memory: 4240kb
input:
100 2000 210 842 651 837 310 306 379 70 812 254 470 986 716 758 877 810 479 2 37 95 420 553 294 104 ...
output:
921457984
result:
ok "921457984"
Test #23:
score: 4
Accepted
time: 440ms
memory: 4240kb
input:
100 2000 262384517 408485232 462647781 418679432 650998123 641852238 922256756 641803137 509515608 8...
output:
894728423
result:
ok "894728423"
Test #24:
score: 4
Accepted
time: 434ms
memory: 4328kb
input:
100 2000 262384517 408485232 462647781 418679432 650998123 641852238 922256756 641803137 509515608 8...
output:
894728423
result:
ok "894728423"
Test #25:
score: 4
Accepted
time: 446ms
memory: 4288kb
input:
100 2000 56990606 120764782 987023244 156836157 842608604 208464159 567237759 712237317 913798582 78...
output:
324904243
result:
ok "324904243"