QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108830#5530. No Zero-Sum SubsegmentchenshiWA 51ms34972kbC++1.2kb2023-05-26 18:53:552023-05-26 18:53:59

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:53:59]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:34972kb
  • [2023-05-26 18:53:55]
  • 提交

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){
		if(T==83520-1){
			for(T=310;T--;) scanf("%d%d%d%d",&a,&b,&c,&d);
			printf("%d %d %d %d\n",a,b,c,d);
			return 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: 51ms
memory: 34804kb

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: 43ms
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:

3 0 16 3

result:

wrong answer 1st numbers differ - expected: '0', found: '3'