题解 CF451E 【Devu and Flowers】

2018-07-09 21:11:24


首先,一句话题意:

有$s$个球,$n$个盒子,第$i$个盒子最多能放$f[i]$个球,也可以不放,问放球的方法总数模$10^9+7$的模数。


如果盒子没有容纳限制,那么这个题就是一道经典的组合数学题,答案直接$C^{n-1}_ {s+n-1}$,但这道题有$f$的限制,比较讨厌。

下面介绍两种方法。

1.母函数

这题的母函数很容易表示出来,为

$f(x)=(1+x^1+x^2\dots+x^{f[1]})(1+x^1+x^2\dots+x^{f[2]})\dots(1+x^1+x^2\dots+x^{f[n]})$

答案则为$x^s$项的系数,可惜此题中$f[i]$很大,因此不能使用母函数。

我着重介绍以下的方法

2.状压+组合数+容斥原理+Lucas定理

注意到除了$n$以外的数都特别大,而$n$特别小,只有$n<=20$。这让我们联想到了状态压缩,$2^{20}$的状态大小可以承受。

因此,我们枚举状态$k$。第$i$位表示第$i$个盒子是否放了超过其容量的球。考虑逆向求解,则答案为方案总数-不合法方案总数

方案总数比较简单,为$C^{n-1}_ {s+n-1}$。如果第$i$个盒子放的球数超过了其容量,那么显然,它至少放了$f[i]+1$个球。

我们将所有多放的球从总数中剔除出去,则剩下$m=s-\sum_{i\in k}{(f[i]+1)}$个球,且此时已经满足所有属于$k$的$i$号盒子都超过了其容量。如果有$s<m$,则跳过这种情况,否则共有$C^{n-1}_ {s-m+n-1}$种情况。

for (int i=0;i<(1<<n);i++) {
    LL cnt=s;
    for (int j=1;j<=n;j++)
        if (i&(1<<(j-1))) 
            cnt-=f[j]+1;
    if (cnt<0) continue;
    res=(res+C(cnt+n-1,n-1))%mod;
}

但注意,这并不是最终的答案,因为假如我们计算出了一个放满了$l$个盒子的解,其实这个解的含义是“至少放满了$l$个盒子”,也就是说,它包含放满$l,l+1,l+2\dots n$个盒子的答案,明显有重复。

所以我们使用容斥原理,若状态中有奇数个盒子超出了范围,那么就在$res$中减,否则就加。

for (int i=0;i<(1<<n);i++) {
    LL cnt=s;int del=1;
    for (int j=1;j<=n;j++)
        if (i&(1<<(j-1))) 
            cnt-=f[j]+1,del=-del;
    if (cnt<0) continue;
    res=(res+C(cnt+n-1,n-1)*(LL)del)%mod;
}

最后说一下Lucas定理:解决大组合数取模。注意此题中组合数的第一项是一个可能为$10^{14}$的数,不能使用常规方法。

LL Lucas(LL a,LL b) {
    if (a<=mod&&b<=mod) return C(a,b);
    return C(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;//Lucas
}

附上AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
const LL mod=1e9+7;
LL Pow(LL x,LL y) {
    LL res=1;
    while (y) {
        if (y&1) res=res*x%mod;
        x=x*x%mod,y>>=1;
    }
    return res;
}
LL C(int n,int r) {
    if (n<r) return 0;
    r=min(r,n-r);
    LL res=1,a=1,b=1;
    for (int i=1;i<=r;i++)
        a=a*(n-i+1)%mod,b=b*i%mod;
    res=res*a%mod*Pow(b,mod-2)%mod;
    return res;
}
LL Lucas(LL a,LL b) {
    if (a<=mod&&b<=mod) return C(a,b);
    return C(a%mod,b%mod)*Lucas(a/mod,b/mod)%mod;
}
LL f[21];
LL solve(int n,LL s) {
    LL res=0;
    for (int i=0;i<(1<<n);i++) {
        LL cnt=s;int del=1;
        for (int j=1;j<=n;j++)
            if (i&(1<<(j-1))) 
                cnt-=f[j]+1,del=-del;
        if (cnt<0) continue;
        res=(res+Lucas(cnt+n-1,n-1)*(LL)del)%mod;
    }
    return (res+mod)%mod;
}
int main() {
    int n;LL s;
    while (~scanf("%d%lld",&n,&s)) {
        for (int i=1;i<=n;i++) scanf("%lld",&f[i]);
        printf("%lld\n",solve(n,s));
    }
}