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
#define fi first
#define se second
#define debug cout<<"I AM HERE"<>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