QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108837 | #5530. No Zero-Sum Subsegment | chenshi | WA | 89ms | 34972kb | C++ | 1.1kb | 2023-05-26 19:01:19 | 2023-05-26 19:01:23 |
Judging History
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=(1+(b>1||c>1))*2*(!b||!c);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: 55ms
memory: 34860kb
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: 89ms
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 378th numbers differ - expected: '5', found: '4'