Luogu CF451E Devu and Flowers 题解报告

题目传送门

【题目大意】

有n种颜色的花，第i种颜色的花有a[i]朵，从这些花中选m朵出来，问有多少种方案？答案对10⁹+7取模

【思路分析】

这是一个多重集的组合数问题，答案就是：$$C_{n+m-1}^{n-1}-\sum_{i=1}^{n}C_{n+m-a[i]-2}^{n-1}+\sum_{1\le i<j\le n}C_{n+m-a[i]-a[j]-3}^{n-1}-…+(-1)^nC_{n+m-\sum_{i=1}^{n}a[i]-(n+1)}^{n-1}$$

在具体实现的时候，我们可以枚举x=0~2ⁿ-1，若x在二进制表示下共有p位为1，分别是第i[1],i[2]…i[p]位，则这个x就代表上式中的这一项：$$(-1)^pC_{n+m-a[i[1]]-a[i[2]]-…-a[i[p]]-(p+1)}^{n-1}$$

这样我们就可以成功地得到容斥原理计算多重集组合数的公式的每一项。

【代码实现】

#include<bits/stdc++.h>
#define ll long long
#define go(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
ll a[22],m,ans=0;
int inv[22],n;
const int mod=1e9+7;
int ksm(int x,int y){
    int as=1;
    while(y){
        if(y&1) as=(ll)as*x%mod;
        x=(ll)x*x%mod;
        y>>=1;
    }
    return as;
}
int C(ll y,int x){//计算组合数
    if(y<0||x<0||x>y) return 0;
    y%=mod;
    if(y==0||x==0) return 1;
    int as=1;
    go(i,0,x-1) as=(ll)as*(y-i)%mod;
    go(i,1,x) as=(ll)as*inv[i]%mod;
    return as;
}
int main(){
    go(i,1,20) inv[i]=ksm(i,mod-2);//预处理逆元
    scanf("%d%lld",&n,&m);
    go(i,1,n) scanf("%lld",&a[i]);
    for(int x=0;x<(1<<n);x++){//枚举x
        if(x==0) ans=(ans+C(n+m-1,n-1))%mod;
        else {
            ll t=n+m;
            int p=0;
            go(i,0,n-1)
                if((x>>i)&1) p++,t-=a[i+1];
            t-=p+1;
            if(p&1) ans=(ans-C(t,n-1))%mod;
            else ans=(ans+C(t,n-1))%mod;
        }
    }
    cout<<(ans+mod)%mod<<endl;
    return 0;
}