Logo Wy Online Judge

WyOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#933#210. 「CSP-S2019」Emiya 家今天的饭ryp100621ms5188kbC++141.5kb2025-07-04 17:09:452025-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"