UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138779#239. countjohnson2007105832ms157444kbC++956b2021-10-02 10:08:332021-10-02 10:08:33

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7+5;
const ll mod=998244353;
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(fac[n]*(inv[m]*inv[n-m])%mod)%mod;
	else{
		ll ret=inv[m];
		for(ll i=n;i>=n-m+1;i--)ret=(ret*(i%mod))%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=(g(n-i*k,m)*C(m,i))%mod;
		ans=(i%2)?(ans-ret+mod)%mod:(ans+ret)%mod;//容斥
	}
	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]=(fac[i-1]*i)%mod;
	for(ll i=2;i<N;i++)inv[i]=((mod-mod/i)*inv[mod%i])%mod;
	for(ll i=2;i<N;i++)inv[i]=(inv[i]*inv[i-1])%mod;
	//小于m 
	
	ll ans=0;
	for(ll i=0;i<k;i++)
		ans=(ans+(f(i*m+n%m,k,m-1)*g((n-n%m)/m-i,k))%mod)%mod;
	cout<<ans;
	return 0;
}

Details

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

Test #1:

score: 0
Wrong Answer
time: 505ms
memory: 157440kb

input:

1000 1000 3


output:

103261800

result:

wrong answer 1st lines differ - expected: '498501', found: '103261800'

Test #2:

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

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

score: 0
Wrong Answer
time: 590ms
memory: 157440kb

input:

1999 1005 3


output:

857607642

result:

wrong answer 1st lines differ - expected: '1992024', found: '857607642'

Test #4:

score: 0
Wrong Answer
time: 536ms
memory: 157444kb

input:

523098578902387543 1990 3


output:

573830341

result:

wrong answer 1st lines differ - expected: '741828632', found: '573830341'

Test #5:

score: 0
Wrong Answer
time: 563ms
memory: 157440kb

input:

985435493875384653 1987 3

output:

455923951

result:

wrong answer 1st lines differ - expected: '930955578', found: '455923951'

Test #6:

score: 0
Wrong Answer
time: 590ms
memory: 157444kb

input:

854378965978354365 4898 20


output:

902687568

result:

wrong answer 1st lines differ - expected: '72755158', found: '902687568'

Test #7:

score: 0
Wrong Answer
time: 535ms
memory: 157440kb

input:

869347685748976465 5000 20


output:

935573213

result:

wrong answer 1st lines differ - expected: '946187174', found: '935573213'

Test #8:

score: 0
Wrong Answer
time: 634ms
memory: 157440kb

input:

985493567483653416 4999 2000


output:

362063712

result:

wrong answer 1st lines differ - expected: '715344547', found: '362063712'

Test #9:

score: 0
Wrong Answer
time: 640ms
memory: 157444kb

input:

1000000000000000000 4987 1992


output:

587270423

result:

wrong answer 1st lines differ - expected: '142311097', found: '587270423'

Test #10:

score: 0
Wrong Answer
time: 678ms
memory: 157440kb

input:

666666666623333333 4998 1999


output:

674398615

result:

wrong answer 1st lines differ - expected: '7913341', found: '674398615'