Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#949#210. 「CSP-S2019」Emiya 家今天的饭FiraCode1001848ms4328kbC++141.2kb2025-07-05 08:35:212025-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"