M. 810975 题解(容斥)

题目链接

题目思路

题目可以转化为有\(n-m+1\)个数，每个数\(0\leq x_i \leq k\) 并且这些数的和为\(m\) 且数的最大值为\(k\)

那么可以再转化为

有\(n-m+1\)个数，每个数\(0\leq x_i \leq k\) 并且这些数的和为\(m\)

减去有\(n-m+1\)个数，每个数\(0\leq x_i \leq k-1\) 并且这些数的和为\(m\)

就是这个问题链接

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=3e5+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k;
ll fac[maxn],finv[maxn];
ll qpow(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b=b>>1;
    }
    return ans;
}
void init(int n){
    fac[0]=finv[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    finv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=1;i--){
        finv[i]=finv[i+1]*(i+1)%mod;
    }
}
ll c(ll a,ll b){
    if(a<b||a<0||b<0) return 0;
    ll ans=fac[a]*finv[b]%mod*finv[a-b]%mod;
    return ans;
}
ll cal(int num,int lim,int sum){
    ll ans=0;
    ll flag=-1;
    for(ll i=0;i<=num;i++){
        flag*=-1;
        ans=(ans+flag*c(num,i)*c(num+sum-1-i*lim,num-1))%mod;
    }
    ans=(ans%mod+mod)%mod;
    return ans;
}
signed main(){
    init(200000);
    scanf("%d%d%d",&n,&m,&k);
    int num=n-m+1;
    int lim=k;
    int sum=m;
    ll ans=(cal(num,lim+1,sum)-cal(num,lim,sum)+2*mod)%mod;
    printf("%lld\n",ans);
    return 0;
}