UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138785#239. countgzhhtao00ms0kbC++1012b2021-10-02 10:22:032021-10-02 10:22:04

answer

#include<iostream>
using namespace std;
const long long mod=998244353;
long long n,m,k,xx,yy,fc[1000010],iv[1000010],ans;
long long pw(long long x){
	long long ans=1;
	for(long long i=mod-2;i;i>>=1,x=x*x%mod){
		if(i&1){
			ans=ans*x%mod;
		}
	}
	return ans;
}
long long C(long long x,long long y){
	if(x<xx){
		return iv[y]*iv[x-y]%mod*fc[x]%mod;
	}
	long long ans=iv[y];
	for(long long i=0;i<y;i++){
		ans=(x-i)%mod*ans%mod;
	}
	return ans;
}
long long F(long long x){
	if(x<0){
		return 0;
	}
	long long ans=0,y;
	for(long long i=0;i<=k;i++){
		y=C(k,i)*C(x-i*(m-1)+k-1,k-1)%mod;
		ans=(ans+(i&1?mod-1:1)*y%mod)%mod;
	}
	return ans;
}
int main(){
	cin>>n>>m>>k;
	xx=k*m;yy=n%m;
	if(!m){
		cout<<"0";
		return 0;
	}
	fc[0]=1;
	for(long long i=1;i<=n;i++){
		fc[i]=fc[i-1]*i%mod;
	}
	iv[n]=pw(fc[n]);
	for(long long i=n;i>=1;i--){
		iv[i-1]=iv[i]*i%mod;
	}
	for(long long i=0;i<=k;i++){
		ans=(ans+F(i*m+yy-k)*C((n-yy)/m-i+k-1,k-1)%mod)%mod;
	}
	cout<<ans;
}

Details

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

Test #1:

score: 0
Runtime Error

input:

1000 1000 3


output:


result:


Test #2:

score: 0
Runtime Error

input:

2000 2000 2


output:


result:


Test #3:

score: 0
Runtime Error

input:

1999 1005 3


output:


result:


Test #4:

score: 0
Runtime Error

input:

523098578902387543 1990 3


output:


result:


Test #5:

score: 0
Runtime Error

input:

985435493875384653 1987 3

output:


result:


Test #6:

score: 0
Runtime Error

input:

854378965978354365 4898 20


output:


result:


Test #7:

score: 0
Runtime Error

input:

869347685748976465 5000 20


output:


result:


Test #8:

score: 0
Runtime Error

input:

985493567483653416 4999 2000


output:


result:


Test #9:

score: 0
Runtime Error

input:

1000000000000000000 4987 1992


output:


result:


Test #10:

score: 0
Runtime Error

input:

666666666623333333 4998 1999


output:


result: