UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#148190#239. countchsuhan3048ms2752kbC++111.2kb2022-04-16 14:43:232022-04-16 14:43:24

answer

#include<bits/stdc++.h>
#define ll long long
#define inf 1e9
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define per(i,r,l) for(register int i=r;i>=l;--i)
using namespace std;
const int N=1e5+10,Mod=998244353;

ll n,m,k;
ll jc[N],jc_inv[N];
ll ans,lim;
inline ll ksm(ll a,ll b){
	ll ret=1;
	while (b){
		if(b&1)ret=ret*a%Mod;
		a=a*a%Mod;
		b>>=1;
	}
	return ret%Mod;
} 
inline void init(){
	jc[0]=jc_inv[0]=1;
	rep(i,1,100000){
		jc[i]=jc[i-1]*i%Mod;
		jc_inv[i]=ksm(jc[i],Mod-2);
	}
	//rep(i,1,10)cout<<jc_inv[i]<<' ';cout<<endl;
}
inline ll C(ll n,ll m){
	if(n<0||m<0||n<m)return 0;
	if(n<=1e5)return jc[n]*jc_inv[m]%Mod*jc_inv[n-m]%Mod;
	else{
		ll ret=jc_inv[m];
		rep(i,n-m+1,n)ret=ret*i%Mod;
		return ret;
	}
}
inline ll g(ll n,ll m){
	if(n<0)return 0;
	return C(n+m-1,m-1);
}
inline ll f(ll n,ll m,ll k){
	n-=m;
	if(n<0)return 0;
	ll ret=0;
	rep(i,0,m){
		ll w=(i&1)?-1:1;
		ret=(ret+w*g(n-i*k,m)*C(m,i)%Mod)%Mod;
		ret=(ret+Mod)%Mod;
	}
	return ret;
}
int main(){
	init();
	scanf("%lld%lld%lld",&n,&m,&k);
	lim=n%m;
	rep(i,0,k-1)ans=(ans+f(i*m+lim,k,m-1)*g((n-lim)/m-i,k)%Mod)%Mod;
	printf("%lld\n",ans);
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 14ms
memory: 2748kb

input:

1000 1000 3


output:

498501

result:

ok single line: '498501'

Test #2:

score: 10
Accepted
time: 17ms
memory: 2748kb

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

score: 10
Accepted
time: 17ms
memory: 2752kb

input:

1999 1005 3


output:

1992024

result:

ok single line: '1992024'

Test #4:

score: 0
Time Limit Exceeded

input:

523098578902387543 1990 3


output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

985435493875384653 1987 3

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

854378965978354365 4898 20


output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

869347685748976465 5000 20


output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

985493567483653416 4999 2000


output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

1000000000000000000 4987 1992


output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

666666666623333333 4998 1999


output:


result: