QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#876939 | #10014. Bottles | rotcar07 | AC ✓ | 27ms | 5888kb | C++23 | 1.1kb | 2025-01-31 15:36:34 | 2025-01-31 15:36:35 |
Judging History
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'