QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108828#5530. No Zero-Sum SubsegmentchenshiWA 79ms34972kbC++1.1kb2023-05-26 18:52:022023-05-26 18:52:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-26 18:52:04]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:34972kb
  • [2023-05-26 18:52:02]
  • 提交

answer

#include<cstdio>
#include<iostream>
using namespace std;
const int o=4e6+10,MOD=998244353;
int T,fac[o],inv[o],a,b,c,d,ans;
inline int C(int x,int y){if(x<y||y<0) return 0;return fac[x]*1ll*inv[y]%MOD*inv[x-y]%MOD;}
int main(){
	inv[1]=1;
	for(int i=2;i<o;++i) inv[i]=MOD-MOD/i*1ll*inv[MOD%i]%MOD;
	for(int i=fac[0]=inv[0]=1;i<o;++i) fac[i]=fac[i-1]*1ll*i%MOD,inv[i]=inv[i-1]*1ll*inv[i]%MOD;
	for(scanf("%d",&T);T--;printf("%d\n",ans),ans=0){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(!a&&!b){ans=C(c+d,c);continue;}
		if(!c&&!d){ans=C(a+b,a);continue;}
		if(!a&&!d) continue;
		if(!b&&!c) continue;
		if(a<d) swap(a,d),swap(b,c);
		if(!d){ans=C(a+1-(c-1),c)*1ll*C(a+1-c+b-1,b)%MOD;continue;}
		if(b+c==1){ans=2;continue;}
		if(a==d){ans=2*!b;continue;}
		for(int i=0;i<2;++i){
			b-=i;c-=!i;
			if(b>=0&&c>=0) ans=(ans+C(a-d-1+i-(c-1),c)*2ll*C(a-d+i-c+b-1,b))%MOD;
			b+=i;c+=!i;
		}
		for(int i=0;i<2;++i) for(int j=0;j<2;++j){
			b-=i+j;c-=(!i)+(!j);
			if(b>=0&&c>=0) ans=(ans+C(a-d-3+i+j-(c-1),c)*1ll*C(a-d-1+i+j-c+b-1,b)%MOD*(d-1))%MOD;
			b+=i+j;c+=(!i)+(!j);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 35ms
memory: 34884kb

input:

5
69 0 0 0
1 1 1 1
0 0 3 3
6 1 0 6
10000 10000 1000000 1000000

output:

1
0
20
2
480402900

result:

ok 5 number(s): "1 0 20 2 480402900"

Test #2:

score: -100
Wrong Answer
time: 79ms
memory: 34972kb

input:

83520
13 1 6 8
13 9 3 14
1 16 13 0
8 12 7 16
10 5 9 15
16 16 15 1
5 11 0 4
12 4 11 15
16 7 1 10
2 6 3 3
15 14 12 0
0 8 12 12
3 0 6 7
16 2 16 15
16 16 16 13
8 13 2 14
7 9 7 0
9 8 4 6
13 16 4 11
11 1 12 4
7 9 4 16
12 13 0 4
5 0 9 1
11 11 0 3
1 11 14 3
3 3 7 3
8 5 4 4
6 7 12 14
2 11 5 6
15 4 9 14
15 11...

output:

0
0
0
0
0
0
52
0
26784
0
0
0
392
0
0
0
0
0
0
0
0
478686
0
136136
0
0
0
0
0
0
0
1680
0
821
0
24024
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8994258
0
0
0
0
0
293930
0
0
156637
166
0
0
0
0
0
0
0
0
0
54
0
0
1248
126
0
0
0
344
0
9867
10880
544
0
0
0
0
0
216580
0
0
4620
0
0
0
0
0
57915
0
0
0
10
0
72442440
0
1085473...

result:

wrong answer 310th numbers differ - expected: '4', found: '2'