UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203187#3546. countsjc0610311003832ms65352kbC++112.4kb2024-02-20 10:46:292024-02-20 13:44:12

answer

#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;

int r[4000010],w[4000010];

int pw[2000010],rev[2000010],rr[2000010];

inline void add1(int &x,int y)
{
	x+=y;
	if(x>=MOD) x-=MOD;
}

inline void add2(int &x,int y)
{
	x+=y;
	if(x<0) x+=MOD;
}

inline int my_pow(int x,int y)
{
	if(y==0) return 1;
	if(y==1) return x;
	int res=my_pow(x,y/2);
	if(y%2==0) return 1ll*res*res%MOD;
	else return 1ll*res*res%MOD*x%MOD;
}

inline int calc(int x,int y)
{
	if(x<y) return 0;
	return 1ll*pw[x]*rev[y]%MOD*rev[x-y]%MOD;
}

inline void init()
{
	for(int i=1;i<22;i++){
		int wn=my_pow(3,(MOD-1)/(1<<i)),now=1;
		for(int j=0;j<(1<<(i-1));j++){
			w[(1<<(i-1))+j]=now;
			now=1ll*now*wn%MOD;
		}
	}
}

inline void NTT(vector<int> &a)
{
	int n=(int)a.size();
	int p=1,k=0;
	while(p<n) p*=2,k++;
	for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(k-1));
	for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<=k;i++){
		for(int j=0;j<(1<<k);j+=(1<<i)){
			int off=(1<<(i-1));
			for(int l=j;l<j+off;l++){
				int x=a[l],y=1ll*a[l+off]*w[off+l-j]%MOD;
				a[l]=(x+y>=MOD)?x+y-MOD:x+y;
				a[l+off]=(x-y<0)?x-y+MOD:x-y;
			}
		}
	}
}

inline vector<int> convolution(vector<int> a,vector<int> b)
{
	int n=(int)a.size(),m=(int)b.size();
	int k=1;
	while(k<n+m) k*=2;
	a.resize(k);b.resize(k);
	NTT(a);NTT(b);
	for(int i=0;i<k;i++) a[i]=1ll*a[i]*b[i]%MOD;
	NTT(a);
	reverse(a.begin()+1,a.end());
	a.resize(n+m-1);
	int rev=my_pow(k,MOD-2);
	for(int i=0;i<n+m-1;i++) a[i]=1ll*a[i]*rev%MOD;
	return a;
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	init();
	int n,k,x;cin>>n>>k>>x;
	pw[0]=1;
	for(int i=1;i<=2*n;i++) pw[i]=1ll*pw[i-1]*i%MOD;
	rev[2*n]=my_pow(pw[2*n],MOD-2);
	for(int i=2*n-1;i>=0;i--) rev[i]=1ll*rev[i+1]*(i+1)%MOD;
	rr[1]=1;
	for(int i=2;i<=2*n;i++) rr[i]=MOD-1ll*(MOD/i)*rr[MOD%i]%MOD;
	if(k==1){
		cout<<pw[n]<<'\n';
		return 0;
	}
	int ans=0,sum=0;
	add1(ans,pw[n-1]);
	for(int i=2;i<=n;i++){
		add1(sum,1ll*calc(i-1+k-2,k-2)*(i-1)%MOD);
		int now=1ll*pw[n-i]*pw[i-2]%MOD*calc(n-x,i-1)%MOD;
		add1(ans,1ll*now*sum%MOD);
	}
	vector<int> v1,v2,v3;
	for(int i=1;i<=n;i++) v1.push_back(i-1);
	for(int i=n;i>=2;i--) v2.push_back(rr[i-1]);
	v3=convolution(v1,v2);
	for(int i=0;i<=n-1;i++){
		int cur=1ll*pw[n-1]*calc(i+k-2,k-2)%MOD;
		cur=1ll*cur*v3[n-1-i]%MOD;
		add1(ans,cur);
	}
	cout<<ans<<'\n';
	return 0;
}

Details

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

Test #1:

score: 5
Accepted
time: 11ms
memory: 9480kb

input:

7 3 7

output:

20640

result:

ok single line: '20640'

Test #2:

score: 5
Accepted
time: 14ms
memory: 9484kb

input:

7 2 6

output:

10560

result:

ok single line: '10560'

Test #3:

score: 5
Accepted
time: 14ms
memory: 9488kb

input:

178 88 176

output:

263756452

result:

ok single line: '263756452'

Test #4:

score: 5
Accepted
time: 10ms
memory: 9488kb

input:

165 64 151

output:

675678116

result:

ok single line: '675678116'

Test #5:

score: 5
Accepted
time: 11ms
memory: 9492kb

input:

188 83 184

output:

69478022

result:

ok single line: '69478022'

Test #6:

score: 5
Accepted
time: 8ms
memory: 9492kb

input:

158 62 144

output:

203749473

result:

ok single line: '203749473'

Test #7:

score: 5
Accepted
time: 5ms
memory: 9616kb

input:

1974 459 1845

output:

535987457

result:

ok single line: '535987457'

Test #8:

score: 5
Accepted
time: 5ms
memory: 9616kb

input:

1970 499 1944

output:

118089661

result:

ok single line: '118089661'

Test #9:

score: 5
Accepted
time: 10ms
memory: 9608kb

input:

1962 195 1766

output:

563043519

result:

ok single line: '563043519'

Test #10:

score: 5
Accepted
time: 15ms
memory: 9608kb

input:

1957 408 1858

output:

368025374

result:

ok single line: '368025374'

Test #11:

score: 5
Accepted
time: 379ms
memory: 65348kb

input:

999966 2907 1

output:

891313743

result:

ok single line: '891313743'

Test #12:

score: 5
Accepted
time: 375ms
memory: 65352kb

input:

999997 4828 2

output:

815004193

result:

ok single line: '815004193'

Test #13:

score: 5
Accepted
time: 387ms
memory: 65348kb

input:

999959 5271 2

output:

600125008

result:

ok single line: '600125008'

Test #14:

score: 5
Accepted
time: 397ms
memory: 65348kb

input:

999961 24134 10

output:

784444417

result:

ok single line: '784444417'

Test #15:

score: 5
Accepted
time: 384ms
memory: 65348kb

input:

999983 33966 10

output:

744109998

result:

ok single line: '744109998'

Test #16:

score: 5
Accepted
time: 375ms
memory: 65352kb

input:

999951 31503 999934

output:

518818294

result:

ok single line: '518818294'

Test #17:

score: 5
Accepted
time: 362ms
memory: 65348kb

input:

999953 21775 999941

output:

459927485

result:

ok single line: '459927485'

Test #18:

score: 5
Accepted
time: 365ms
memory: 65348kb

input:

999970 7889 999782

output:

979137112

result:

ok single line: '979137112'

Test #19:

score: 5
Accepted
time: 361ms
memory: 65352kb

input:

999972 6809 999964

output:

64469239

result:

ok single line: '64469239'

Test #20:

score: 5
Accepted
time: 344ms
memory: 65348kb

input:

999952 29898 999948

output:

801924273

result:

ok single line: '801924273'

Extra Test:

score: 0
Extra Test Passed