UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138781#239. countjohnson20071005921ms157444kbC++1015b2021-10-02 10:09:572021-10-02 10:09:58

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7 + 5;
const ll mod=998244353;
ll add(ll a,ll b){ return (a+b)%mod;}
ll mul(ll a,ll b){ return (a*b)%mod;}
ll n,m,k,fac[N],inv[N];
ll C(ll n,ll m){
	if(n<0||m<0||n<m) return 0;
	if(n<N) return mul(fac[n],mul(inv[m],inv[n-m]));
	else{
		ll ret=inv[m];
		for(ll i=n;i >= n-m + 1;i--) ret=mul(ret,i % mod);
		return ret;
	}
}
ll g(ll n,ll m){ 
	if(n<0) return 0;
	return C(n + m-1,m-1);
}
ll f(ll n,ll m,ll k){
	n-=m;
	if(n<0)return 0;
	ll ans=0;
	for(ll i=0;i<=m;i++){
		ll ret=mul(g(n-i*k,m),C(m,i));
		(i%2)?ans=add(ans,mod-ret):(ans=add(ans,ret)); 
	}
	return ans;
}
int main(){
	cin>>n>>m>>k;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(ll i=2;i<N;i++) fac[i]=mul(fac[i-1],i);
	for(ll i=2;i<N;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
	for(ll i=2;i<N;i++) inv[i]=mul(inv[i],inv[i-1]);
	ll ans=0;
	for(ll i=0;i<k;i++){
		ans=add(ans,mul(f(i*m+n%m,k,m-1),g((n-n%m)/m-i,k)));
	}
	cout<<ans;
	return 0;
}

Details

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

Test #1:

score: 10
Accepted
time: 536ms
memory: 157444kb

input:

1000 1000 3


output:

498501

result:

ok single line: '498501'

Test #2:

score: 10
Accepted
time: 601ms
memory: 157444kb

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

score: 10
Accepted
time: 592ms
memory: 157440kb

input:

1999 1005 3


output:

1992024

result:

ok single line: '1992024'

Test #4:

score: 10
Accepted
time: 568ms
memory: 157440kb

input:

523098578902387543 1990 3


output:

741828632

result:

ok single line: '741828632'

Test #5:

score: 10
Accepted
time: 516ms
memory: 157444kb

input:

985435493875384653 1987 3

output:

930955578

result:

ok single line: '930955578'

Test #6:

score: 10
Accepted
time: 578ms
memory: 157444kb

input:

854378965978354365 4898 20


output:

72755158

result:

ok single line: '72755158'

Test #7:

score: 10
Accepted
time: 547ms
memory: 157440kb

input:

869347685748976465 5000 20


output:

946187174

result:

ok single line: '946187174'

Test #8:

score: 10
Accepted
time: 654ms
memory: 157444kb

input:

985493567483653416 4999 2000


output:

715344547

result:

ok single line: '715344547'

Test #9:

score: 10
Accepted
time: 674ms
memory: 157444kb

input:

1000000000000000000 4987 1992


output:

142311097

result:

ok single line: '142311097'

Test #10:

score: 10
Accepted
time: 655ms
memory: 157444kb

input:

666666666623333333 4998 1999


output:

7913341

result:

ok single line: '7913341'