UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203182#3546. countshr1001164ms20788kbC++11969b2024-02-20 10:29:002024-02-20 13:43:58

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5,mod=998244353;
int n,k,X,ans,p[N],iv[N],f[N];
inline void fix(int&x) {if(x>=mod) x-=mod;}
int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
	return res;
}
int c(int x,int y){
	if(x<y||y<0) return 0;
	return 1ll*p[x]*iv[y]%mod*iv[x-y]%mod;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>k>>X;
	for(int i=p[0]=1;i<N;i++) p[i]=1ll*i*p[i-1]%mod;
	iv[N-1]=qpow(p[N-1],mod-2);
	for(int i=N-2;~i;i--) iv[i]=iv[i+1]*(i+1ll)%mod;
	if(X==1) ans=1ll*p[n-1]*c(k+n-1,k)%mod;
	else for(int i=2;i<=n;i++) fix(ans+=1ll*p[n-2]*c(k+n-i,k)%mod);
	for(int i=1;i<n;i++)
		fix(ans+=(X-1ll)*c(n-X,i-1)%mod*p[i-1]%mod*p[n-i-1]%mod*c(k+i-1,k)%mod);
	for(int i=f[0]=1;i<n;i++) f[i]=(f[i-1]+c(k+i,k))%mod;
	for(int i=2;i<n;i++)
		fix(ans+=(c(n-1,i)-c(n-X,i)-(X-1ll)*c(n-X,i-1)%mod+mod*2)%mod*p[i-2]%mod*p[n-i-1]%mod*f[i-2]%mod);
	cout<<ans;
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 19ms
memory: 16880kb

input:

7 3 7

output:

20640

result:

ok single line: '20640'

Test #2:

score: 5
Accepted
time: 23ms
memory: 16880kb

input:

7 2 6

output:

10560

result:

ok single line: '10560'

Test #3:

score: 5
Accepted
time: 31ms
memory: 16880kb

input:

178 88 176

output:

263756452

result:

ok single line: '263756452'

Test #4:

score: 5
Accepted
time: 24ms
memory: 16884kb

input:

165 64 151

output:

675678116

result:

ok single line: '675678116'

Test #5:

score: 5
Accepted
time: 33ms
memory: 16884kb

input:

188 83 184

output:

69478022

result:

ok single line: '69478022'

Test #6:

score: 5
Accepted
time: 25ms
memory: 16884kb

input:

158 62 144

output:

203749473

result:

ok single line: '203749473'

Test #7:

score: 5
Accepted
time: 26ms
memory: 16892kb

input:

1974 459 1845

output:

535987457

result:

ok single line: '535987457'

Test #8:

score: 5
Accepted
time: 23ms
memory: 16892kb

input:

1970 499 1944

output:

118089661

result:

ok single line: '118089661'

Test #9:

score: 5
Accepted
time: 27ms
memory: 16888kb

input:

1962 195 1766

output:

563043519

result:

ok single line: '563043519'

Test #10:

score: 5
Accepted
time: 28ms
memory: 16892kb

input:

1957 408 1858

output:

368025374

result:

ok single line: '368025374'

Test #11:

score: 5
Accepted
time: 84ms
memory: 20784kb

input:

999966 2907 1

output:

891313743

result:

ok single line: '891313743'

Test #12:

score: 5
Accepted
time: 101ms
memory: 20784kb

input:

999997 4828 2

output:

815004193

result:

ok single line: '815004193'

Test #13:

score: 5
Accepted
time: 104ms
memory: 20788kb

input:

999959 5271 2

output:

600125008

result:

ok single line: '600125008'

Test #14:

score: 5
Accepted
time: 106ms
memory: 20784kb

input:

999961 24134 10

output:

784444417

result:

ok single line: '784444417'

Test #15:

score: 5
Accepted
time: 106ms
memory: 20788kb

input:

999983 33966 10

output:

744109998

result:

ok single line: '744109998'

Test #16:

score: 5
Accepted
time: 76ms
memory: 20788kb

input:

999951 31503 999934

output:

518818294

result:

ok single line: '518818294'

Test #17:

score: 5
Accepted
time: 85ms
memory: 20784kb

input:

999953 21775 999941

output:

459927485

result:

ok single line: '459927485'

Test #18:

score: 5
Accepted
time: 78ms
memory: 20784kb

input:

999970 7889 999782

output:

979137112

result:

ok single line: '979137112'

Test #19:

score: 5
Accepted
time: 83ms
memory: 20788kb

input:

999972 6809 999964

output:

64469239

result:

ok single line: '64469239'

Test #20:

score: 5
Accepted
time: 82ms
memory: 20784kb

input:

999952 29898 999948

output:

801924273

result:

ok single line: '801924273'

Extra Test:

score: 0
Extra Test Passed