QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#881063 | #10014. Bottles | Kevin5307 | AC ✓ | 79ms | 19448kb | C++23 | 2.1kb | 2025-02-04 10:55:31 | 2025-02-04 10:55:31 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
ll fact[1001000],rfact[1001000];
ll C(int n,int k)
{
if(k<0||k>n) return 0;
return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
ll ksm(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fact[0]=1;
rfact[0]=rfact[1]=1;
for(int i=1;i<1001000;i++) fact[i]=fact[i-1]*i%mod;
for(int i=2;i<1001000;i++) rfact[i]=(mod-mod/i)*rfact[mod%i]%mod;
for(int i=2;i<1001000;i++) rfact[i]=rfact[i]*rfact[i-1]%mod;
int e,p,w,t;
cin>>e>>p>>w>>t;
int n=e+p+w;
ll ans=0;
for(int v=t+1;v<=n+t;v++)
{
ll f=1,g=0;
if(v-t-p+1>=1)
{
f=ksm(n-v+t,p);
g=ksm(n-v+t+1,p);
g=(g+mod-f)%mod;
}
else
{
int bound=v-t;
f=ksm(n-v+t,bound)*fact[n-bound]%mod*rfact[n-p]%mod;
g=ksm(n-v+t+1,bound)*fact[n-bound]%mod*rfact[n-p]%mod;
g=(g+mod-f)%mod;
}
ll f2=1,g2=0;
if(n-min(n,v)<e)
f2=g2=0;
if(v-t-p+1>=1)
{
f2=ksm(n-v+t-e,p);
g2=ksm(n-v+t+1-e,p);
g2=(g2+mod-f2)%mod;
}
else
{
int bound=v-t;
f2=ksm(n-v+t-e,bound)*fact[n-bound-e]%mod*rfact[n-p-e]%mod;
g2=ksm(n-v+t+1-e,bound)*fact[n-bound-e]%mod*rfact[n-p-e]%mod;
g2=(g2+mod-f2)%mod;
}
ll tot=(g*C(e+w,e)-g2*C(n-min(n,v),e)%mod)%mod;
ans=(ans+tot)%mod;
}
ll all=C(e+p+w,e)*C(p+w,p)%mod*fact[p]%mod;
cout<<ans*ksm(all,mod-2)%mod<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 19320kb
input:
1 1 2 1
output:
249561089
result:
ok answer is '249561089'
Test #2:
score: 0
Accepted
time: 17ms
memory: 19320kb
input:
1 1 1 42
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 14ms
memory: 19320kb
input:
2 2 2 2
output:
987152750
result:
ok answer is '987152750'
Test #4:
score: 0
Accepted
time: 51ms
memory: 19320kb
input:
12912 83717 73177 1920
output:
685360162
result:
ok answer is '685360162'
Test #5:
score: 0
Accepted
time: 14ms
memory: 19264kb
input:
1 1 1 3
output:
1
result:
ok answer is '1'
Test #6:
score: 0
Accepted
time: 76ms
memory: 19444kb
input:
100000 100000 100000 100000
output:
884123454
result:
ok answer is '884123454'
Test #7:
score: 0
Accepted
time: 79ms
memory: 19324kb
input:
100000 100000 100000 1
output:
37972278
result:
ok answer is '37972278'
Test #8:
score: 0
Accepted
time: 59ms
memory: 19320kb
input:
100000 100000 1 100000
output:
847064892
result:
ok answer is '847064892'
Test #9:
score: 0
Accepted
time: 16ms
memory: 19320kb
input:
100000 1 100000 100000
output:
847064892
result:
ok answer is '847064892'
Test #10:
score: 0
Accepted
time: 62ms
memory: 19316kb
input:
1 100000 100000 100000
output:
151826985
result:
ok answer is '151826985'
Test #11:
score: 0
Accepted
time: 15ms
memory: 19320kb
input:
100000 1 1 1
output:
587783175
result:
ok answer is '587783175'
Test #12:
score: 0
Accepted
time: 40ms
memory: 19320kb
input:
1 100000 1 1
output:
659649092
result:
ok answer is '659649092'
Test #13:
score: 0
Accepted
time: 15ms
memory: 19392kb
input:
1 1 100000 1
output:
217932349
result:
ok answer is '217932349'
Test #14:
score: 0
Accepted
time: 15ms
memory: 19444kb
input:
1 1 1 100000
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 52ms
memory: 19320kb
input:
95749 84022 2256 71002
output:
89255997
result:
ok answer is '89255997'
Test #16:
score: 0
Accepted
time: 50ms
memory: 19320kb
input:
66015 47097 73639 95827
output:
928194339
result:
ok answer is '928194339'
Test #17:
score: 0
Accepted
time: 35ms
memory: 19448kb
input:
95944 17006 29658 23200
output:
771575343
result:
ok answer is '771575343'
Test #18:
score: 0
Accepted
time: 32ms
memory: 19320kb
input:
9257 55034 17879 46323
output:
191492058
result:
ok answer is '191492058'
Test #19:
score: 0
Accepted
time: 52ms
memory: 19316kb
input:
76497 54324 46028 86026
output:
796696990
result:
ok answer is '796696990'
Test #20:
score: 0
Accepted
time: 51ms
memory: 19228kb
input:
57314 82829 23655 7714
output:
800572449
result:
ok answer is '800572449'
Test #21:
score: 0
Accepted
time: 38ms
memory: 19320kb
input:
74146 23222 26306 36160
output:
356496909
result:
ok answer is '356496909'
Test #22:
score: 0
Accepted
time: 38ms
memory: 19448kb
input:
25022 46653 31214 67195
output:
598439319
result:
ok answer is '598439319'
Test #23:
score: 0
Accepted
time: 42ms
memory: 19324kb
input:
11126 87011 10322 26510
output:
706916846
result:
ok answer is '706916846'
Test #24:
score: 0
Accepted
time: 30ms
memory: 19320kb
input:
22900 48667 11506 19337
output:
398909903
result:
ok answer is '398909903'
Test #25:
score: 0
Accepted
time: 55ms
memory: 19324kb
input:
11972 87699 84749 79973
output:
505283863
result:
ok answer is '505283863'
Test #26:
score: 0
Accepted
time: 37ms
memory: 19320kb
input:
77951 3071 79294 22287
output:
18979044
result:
ok answer is '18979044'
Test #27:
score: 0
Accepted
time: 38ms
memory: 19320kb
input:
69840 7597 69452 76260
output:
277837253
result:
ok answer is '277837253'
Test #28:
score: 0
Accepted
time: 41ms
memory: 19280kb
input:
76297 26248 57269 89866
output:
1
result:
ok answer is '1'
Test #29:
score: 0
Accepted
time: 45ms
memory: 19324kb
input:
74522 42427 38267 85979
output:
1
result:
ok answer is '1'
Test #30:
score: 0
Accepted
time: 51ms
memory: 19324kb
input:
32742 93389 40961 91991
output:
760235193
result:
ok answer is '760235193'
Test #31:
score: 0
Accepted
time: 46ms
memory: 19448kb
input:
11938 47548 91651 93913
output:
595870233
result:
ok answer is '595870233'
Test #32:
score: 0
Accepted
time: 40ms
memory: 19320kb
input:
25019 42986 53788 13964
output:
919492573
result:
ok answer is '919492573'
Test #33:
score: 0
Accepted
time: 53ms
memory: 19448kb
input:
81219 69788 40243 1125
output:
163847265
result:
ok answer is '163847265'
Test #34:
score: 0
Accepted
time: 23ms
memory: 19448kb
input:
2933 5015 40518 51856
output:
1
result:
ok answer is '1'