UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138790#239. countgzhhtao00ms0kbC++1.0kb2021-10-02 10:29:562021-10-02 10:29:58

answer

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

详细

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

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: