P2260 CF451E Devu and Flowers解题报告

解题报告

---

CF451E Devu and Flowers解题报告：

更好的阅读体验

题意

题意：$n$种颜色，每种颜色$f_i$朵花，需要选择$m$朵花，求有多少种选择方案（两个方案不同当且仅当存在某一种颜色的花数量不同），对$1000000007$取模。
数据范围：$1\leqslant n\leqslant 20,0\leqslant m\leqslant 10^{14}$。

分析

这是一道求多重集合组合数的题目，比较好地考察了容斥原理和组合数计算。

可以抽象出模型：求在一个存在$n$个元素，每个元素有$f_i$个的可重集取出$m$个元素的方案数。

我们令$s_i$为满足第$i$个元素选择的数量在$f_i$以内，且取出了$m$个元素的方案形成的集合，那么我们的答案便是$|\bigcap_{i=1}^n s_i|$。

因为$s_i$是求至多选多少个，所以不是很好求，那么先容斥一波，

$$|\bigcap_{i=1}^n s_i|=|U|-|\bigcup_{i=1}^n\bar{s_i}|$$

全集就是$n$种元素取出$m$个元素的方案数（某个元素可以选出$0$个），直接套公式：$|U|=C_{n+m-1}^{n-1}$（具体可以考虑一种特殊的隔板法，加入$n-1$个球，选择$n-1$个球间隔出$n$个区间，这些区间可以为$0$）

考虑如何求并集，还是不好求，所以继续容斥：

$$|\bigcup_{i=1}^n \bar{s_i}|=\sum_{k=1}^n(-1)^{k-1}\sum_{a_1<a_2<\cdots<a_k}|\bar{s_{a_1}}\cap \bar{s_{a_2}}\cap\cdots\cap \bar{s_{a_k}}|$$

因为$n$很小，所以可以考虑二进制枚举每一种情况，然后问题转移成怎么求某一种元素$i$选的次数要超过$f_i$并取出$m$个元素的方案数。

因为起码要选$f_i+1$个这种元素，所以可以把选出的$m$减去$f_i+1$，这样就转化为全集那里讲的公式了。

然后直接套公式，套在容斥原理里面，就ok了。

最后，因为$m$很大，所以可以吧组合数$C_n^m=\frac{n!}{m!\cdot(n-m)!}$拆开，变为$n\cdot(n-1)\cdot\cdots\cdot(n-m+1)\cdot\frac{1}{m!}$，然后预处理一下就可以了。

代码

#include<stdio.h>
const long long maxn=25,mod=1000000007;
long long i,j,k,m,n,mul=1,ans;
long long finv[maxn],a[maxn];
long long ksm(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)
            res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
long long c(long long n,long long m){
    if(n<0||m<0||m>n)
        return 0;
    n%=mod,m%=mod;
    long long res=1;
    for(long long i=n-m+1;i<=n;i++)
        res=res*i%mod;
    res=res*finv[m]%mod;
    return res;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(i=1;i<=n;i++)
        mul=mul*i%mod;
    finv[n]=ksm(mul,mod-2);
    for(i=n;i>=1;i--)
        finv[i-1]=finv[i]*i%mod;
    ans=c(n+m-1,n-1);
    for(k=1;k<(1<<n);k++){
        long long cnt=0,res=n+m-1;
        for(i=1;i<=n;i++)
            if((k>>(i-1))&1)
                cnt++,res-=a[i]+1;
        ans=(ans-(cnt%2==0? -1:1)*c(res,n-1))%mod;
    }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}