QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108830 | #5530. No Zero-Sum Subsegment | chenshi | WA | 51ms | 34972kb | C++ | 1.2kb | 2023-05-26 18:53:55 | 2023-05-26 18:53:59 |
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){
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'