UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138782#239. countjohnson20071005952ms157444kbC++994b2021-10-02 10:13:262021-10-02 10:13:27

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));
		ans=(i%2)?add(ans,mod-ret):(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;
}

详细

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

Test #1:

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

input:

1000 1000 3


output:

498501

result:

ok single line: '498501'

Test #2:

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

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

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

input:

1999 1005 3


output:

1992024

result:

ok single line: '1992024'

Test #4:

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

input:

523098578902387543 1990 3


output:

741828632

result:

ok single line: '741828632'

Test #5:

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

input:

985435493875384653 1987 3

output:

930955578

result:

ok single line: '930955578'

Test #6:

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

input:

854378965978354365 4898 20


output:

72755158

result:

ok single line: '72755158'

Test #7:

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

input:

869347685748976465 5000 20


output:

946187174

result:

ok single line: '946187174'

Test #8:

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

input:

985493567483653416 4999 2000


output:

715344547

result:

ok single line: '715344547'

Test #9:

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

input:

1000000000000000000 4987 1992


output:

142311097

result:

ok single line: '142311097'

Test #10:

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

input:

666666666623333333 4998 1999


output:

7913341

result:

ok single line: '7913341'