QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876939#10014. Bottlesrotcar07AC ✓27ms5888kbC++231.1kb2025-01-31 15:36:342025-01-31 15:36:35

Judging History

This is the latest submission verdict.

  • [2025-01-31 15:36:35]
  • Judged
  • Verdict: AC
  • Time: 27ms
  • Memory: 5888kb
  • [2025-01-31 15:36:34]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+5,mod=998244353;
int fac[N],inv[N];
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*1ll*a%mod;
        a=a*1ll*a%mod,b>>=1;
    }
    return ans;
}
inline void red(int&x){x>=mod&&(x-=mod);}
int main(){
    int a,b,c,t;cin>>a>>b>>c>>t;t++;
    int n=a+b+c;
    for(int i=fac[0]=1;i<=n;i++) fac[i]=fac[i-1]*1ll*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for(int i=n;i>=1;i--) inv[i-1]=inv[i]*1ll*i%mod;
    int tot=fac[n]*1ll*inv[a]%mod*inv[c]%mod,ans=0;
    for(int i=t;i<=n-a;i++){
        int r=fac[n-i]*1ll*inv[n-i-a]%mod*inv[a]%mod;
        int ra=min(i-t+1,b),rb=b-ra;
        int w1=qpow(n-i-a+t,ra)*1ll*fac[n-i-a+t-1]%mod*inv[n-i-a+t-1-rb]%mod;
        ra=min(i-t+2,b),rb=b-ra;
        int w2=qpow(n-i-a+t-1,ra)*1ll*fac[n-i-a+t-2]%mod*inv[n-i-a+t-2-rb]%mod;
        ans=(ans+r*1ll*(w1+mod-w2))%mod;
        // cout<<i<<' '<<r<<' '<<ra<<' '<<rb<<' '<<w1<<' '<<w2<<' '<<ans<<'\n';
    }
    cout<<(1+mod-ans*1ll*qpow(tot,mod-2)%mod)%mod<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

1 1 2 1

output:

249561089

result:

ok answer is '249561089'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

1 1 1 42

output:

1

result:

ok answer is '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

2 2 2 2

output:

987152750

result:

ok answer is '987152750'

Test #4:

score: 0
Accepted
time: 20ms
memory: 4736kb

input:

12912 83717 73177 1920

output:

685360162

result:

ok answer is '685360162'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

1 1 1 3

output:

1

result:

ok answer is '1'

Test #6:

score: 0
Accepted
time: 14ms
memory: 5888kb

input:

100000 100000 100000 100000

output:

884123454

result:

ok answer is '884123454'

Test #7:

score: 0
Accepted
time: 27ms
memory: 5888kb

input:

100000 100000 100000 1

output:

37972278

result:

ok answer is '37972278'

Test #8:

score: 0
Accepted
time: 2ms
memory: 5120kb

input:

100000 100000 1 100000

output:

847064892

result:

ok answer is '847064892'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4992kb

input:

100000 1 100000 100000

output:

847064892

result:

ok answer is '847064892'

Test #10:

score: 0
Accepted
time: 15ms
memory: 4992kb

input:

1 100000 100000 100000

output:

151826985

result:

ok answer is '151826985'

Test #11:

score: 0
Accepted
time: 1ms
memory: 5616kb

input:

100000 1 1 1

output:

587783175

result:

ok answer is '587783175'

Test #12:

score: 0
Accepted
time: 13ms
memory: 4352kb

input:

1 100000 1 1

output:

659649092

result:

ok answer is '659649092'

Test #13:

score: 0
Accepted
time: 3ms
memory: 5712kb

input:

1 1 100000 1

output:

217932349

result:

ok answer is '217932349'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

1 1 1 100000

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4992kb

input:

95749 84022 2256 71002

output:

89255997

result:

ok answer is '89255997'

Test #16:

score: 0
Accepted
time: 3ms
memory: 4864kb

input:

66015 47097 73639 95827

output:

928194339

result:

ok answer is '928194339'

Test #17:

score: 0
Accepted
time: 4ms
memory: 4736kb

input:

95944 17006 29658 23200

output:

771575343

result:

ok answer is '771575343'

Test #18:

score: 0
Accepted
time: 3ms
memory: 4224kb

input:

9257 55034 17879 46323

output:

191492058

result:

ok answer is '191492058'

Test #19:

score: 0
Accepted
time: 2ms
memory: 4864kb

input:

76497 54324 46028 86026

output:

796696990

result:

ok answer is '796696990'

Test #20:

score: 0
Accepted
time: 15ms
memory: 4864kb

input:

57314 82829 23655 7714

output:

800572449

result:

ok answer is '800572449'

Test #21:

score: 0
Accepted
time: 2ms
memory: 4480kb

input:

74146 23222 26306 36160

output:

356496909

result:

ok answer is '356496909'

Test #22:

score: 0
Accepted
time: 3ms
memory: 4352kb

input:

25022 46653 31214 67195

output:

598439319

result:

ok answer is '598439319'

Test #23:

score: 0
Accepted
time: 9ms
memory: 4480kb

input:

11126 87011 10322 26510

output:

706916846

result:

ok answer is '706916846'

Test #24:

score: 0
Accepted
time: 6ms
memory: 4096kb

input:

22900 48667 11506 19337

output:

398909903

result:

ok answer is '398909903'

Test #25:

score: 0
Accepted
time: 12ms
memory: 4864kb

input:

11972 87699 84749 79973

output:

505283863

result:

ok answer is '505283863'

Test #26:

score: 0
Accepted
time: 8ms
memory: 4736kb

input:

77951 3071 79294 22287

output:

18979044

result:

ok answer is '18979044'

Test #27:

score: 0
Accepted
time: 1ms
memory: 4608kb

input:

69840 7597 69452 76260

output:

277837253

result:

ok answer is '277837253'

Test #28:

score: 0
Accepted
time: 2ms
memory: 4736kb

input:

76297 26248 57269 89866

output:

1

result:

ok answer is '1'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4736kb

input:

74522 42427 38267 85979

output:

1

result:

ok answer is '1'

Test #30:

score: 0
Accepted
time: 8ms
memory: 4864kb

input:

32742 93389 40961 91991

output:

760235193

result:

ok answer is '760235193'

Test #31:

score: 0
Accepted
time: 8ms
memory: 4608kb

input:

11938 47548 91651 93913

output:

595870233

result:

ok answer is '595870233'

Test #32:

score: 0
Accepted
time: 10ms
memory: 4608kb

input:

25019 42986 53788 13964

output:

919492573

result:

ok answer is '919492573'

Test #33:

score: 0
Accepted
time: 16ms
memory: 4992kb

input:

81219 69788 40243 1125

output:

163847265

result:

ok answer is '163847265'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

2933 5015 40518 51856

output:

1

result:

ok answer is '1'