ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#933 | #210. 「CSP-S2019」Emiya 家今天的饭 | ryp | 100 | 621ms | 5188kb | C++14 | 1.5kb | 2025-07-04 17:09:45 | 2025-07-04 17:09:46 |
answer
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<utility>
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int mod=998244353;
const int maxn=105,maxm=2005;
int N,M,A[maxn][maxm],sum[maxn],f[maxn][maxm],g[maxn][maxm];
void solve5() {
LL ans=1ll;
for(int i=1; i<=N; ++i) {
for(int j=1; j<=M; ++j)
sum[i]=(sum[i]+A[i][j])%mod;
ans=(ans*(sum[i]+1))%mod;
}
ans=(ans-1)%mod;
for(int l=1; l<=M; l++) {
memset(f,0,sizeof(f)) ;
f[0][N]=1;
for(int i=1; i<=N; i++) //行
for(int j=-i; j<=i; j++) { //最高与其他的差值为j ,
int k=j+N ;
f[i][k]=(f[i-1][k]+(LL)f[i-1][k-1]*A[i][l]+(LL)f[i-1][k+1]*(sum[i]-A[i][l]))%mod;
}
for(int j=1; j<=N; j++)
ans=(ans-f[N][j+N])%mod;
/*为什么必需容斥呢?直接选择j<=k不对吗?不对:比如最高列是1,那么其他几列总共也选1个。
那么,当统计的最高列出现在其他几列的时候,就和这种情况一样了,会重复统计!
为什么j>k不会重复呢,当前列必其他所有的列的和都高,也就是大于总数的两倍,这样的列不会出现两个以上!
因此需要容斥。
*/
}
if(ans<0)ans+=mod;
printf("%lld",ans);
}
int main() {
// freopen("meal.in","r",stdin);
// freopen("meal.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1; i<=N; ++i)for(int j=1; j<=M; ++j) {
scanf("%d",A[i]+j);
//sum[i]=(sum[i]+A[i][j])*mod;
}
solve5();
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 4
Accepted
time: 1ms
memory: 4436kb
input:
2 2 1 1 1 1
output:
2
result:
ok "2"
Test #2:
score: 4
Accepted
time: 0ms
memory: 4280kb
input:
2 3 1 1 1 1 0 1
output:
4
result:
ok "4"
Test #3:
score: 4
Accepted
time: 0ms
memory: 4216kb
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: 4276kb
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: 4216kb
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: 0ms
memory: 4416kb
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: 4216kb
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: 4432kb
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: 1ms
memory: 4548kb
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: 4548kb
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: 4548kb
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: 1ms
memory: 4384kb
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: 2ms
memory: 4468kb
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: 1ms
memory: 4548kb
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: 4412kb
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: 2ms
memory: 4368kb
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: 18ms
memory: 4328kb
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: 4556kb
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: 18ms
memory: 4544kb
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: 18ms
memory: 4344kb
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: 21ms
memory: 4368kb
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: 122ms
memory: 4984kb
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: 131ms
memory: 5116kb
input:
100 2000 262384517 408485232 462647781 418679432 650998123 641852238 922256756 641803137 509515608 8...
output:
894728423
result:
ok "894728423"
Test #24:
score: 4
Accepted
time: 132ms
memory: 5188kb
input:
100 2000 262384517 408485232 462647781 418679432 650998123 641852238 922256756 641803137 509515608 8...
output:
894728423
result:
ok "894728423"
Test #25:
score: 4
Accepted
time: 132ms
memory: 4968kb
input:
100 2000 56990606 120764782 987023244 156836157 842608604 208464159 567237759 712237317 913798582 78...
output:
324904243
result:
ok "324904243"