Character Encoding题解(容斥)

题目链接

题目思路

计算有多少种方案使得

\(x_1+x_2+...+x_m=k(0\leq x_i \leq n)\)的方案数

假设没有限制，那么根据隔板法就是\(c(m+k-1,m-1)\)

下面考虑容斥

考虑至少有\(i\)个点大于\(n\)，那么取\(i\)个点直接给他先赋值为\(n\)再进行隔板

则方案数为\(c(m,i)*c(m+k-1-i*n,m-1)\)

然后再进行容斥

答案为\(\sum_{i=0}^{i=m}(-1)^i*c(m,i)*c(m+k-1-i*n,m-1)\)

代码

#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;
}
signed main(){
    init(300000);
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d%d",&n,&m,&k);
        ll ans=0;
        ll flag=-1;
        for(ll i=0;i<=m;i++){
            flag*=-1;
            ans=(ans+flag*c(m,i)*c(m+k-1-i*n,m-1))%mod;
        }
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}