QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#881063#10014. BottlesKevin5307AC ✓79ms19448kbC++232.1kb2025-02-04 10:55:312025-02-04 10:55:31

Judging History

This is the latest submission verdict.

  • [2025-02-04 10:55:31]
  • Judged
  • Verdict: AC
  • Time: 79ms
  • Memory: 19448kb
  • [2025-02-04 10:55:31]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'