UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138826#239. countgzhhtao1002975ms79332kbC++111.0kb2021-10-02 11:38:332021-10-02 11:38:34

answer

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

详细

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

Test #1:

score: 10
Accepted
time: 260ms
memory: 79328kb

input:

1000 1000 3


output:

498501

result:

ok single line: '498501'

Test #2:

score: 10
Accepted
time: 244ms
memory: 79328kb

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

score: 10
Accepted
time: 263ms
memory: 79328kb

input:

1999 1005 3


output:

1992024

result:

ok single line: '1992024'

Test #4:

score: 10
Accepted
time: 262ms
memory: 79328kb

input:

523098578902387543 1990 3


output:

741828632

result:

ok single line: '741828632'

Test #5:

score: 10
Accepted
time: 297ms
memory: 79328kb

input:

985435493875384653 1987 3

output:

930955578

result:

ok single line: '930955578'

Test #6:

score: 10
Accepted
time: 260ms
memory: 79328kb

input:

854378965978354365 4898 20


output:

72755158

result:

ok single line: '72755158'

Test #7:

score: 10
Accepted
time: 265ms
memory: 79328kb

input:

869347685748976465 5000 20


output:

946187174

result:

ok single line: '946187174'

Test #8:

score: 10
Accepted
time: 365ms
memory: 79328kb

input:

985493567483653416 4999 2000


output:

715344547

result:

ok single line: '715344547'

Test #9:

score: 10
Accepted
time: 388ms
memory: 79328kb

input:

1000000000000000000 4987 1992


output:

142311097

result:

ok single line: '142311097'

Test #10:

score: 10
Accepted
time: 371ms
memory: 79332kb

input:

666666666623333333 4998 1999


output:

7913341

result:

ok single line: '7913341'