多重集的组合数（容斥原理）——杨子曰数学？题目？

HenryYang · 2019-09-16 23:08:04 · 题解

超链接：数学合集

打完这篇文章的数学公式真的要吐血身亡了……

模板题：CF451E

模板题还可以长这样： 设S=\{n_1*a_1,n_2*a_2,\cdots,n_k*a_k\}是由n_1个a_1，a_2个a_2，\cdots，n_k个s_k组成的多重集。设n=\sum_{i=1}^{k}n_i，对于任意整数r\leq n，从S种去除r个元素组成一个多重集（不考虑顺序），求产生的不同多重集的数量

上面说的都是同一个问题，我用人话来描述一遍，现在有k堆珠子，每堆珠子颜色不同，第i堆珠子有n_i颗，现在我们从所有的珠子中取出r颗，问你这r颗珠子有多少种搭配？（与顺序无关）

咱们正式开始：

这道题太难了，我们先来解决一个简单一点的问题：我们不管n_i这个条件，也就是说每种珠子都有无穷多颗，那么取r颗能有多少中选择捏？

解决这个问题，我们使用一种非常优美的算法——隔板法

比如r=8,k=3

想法很简单：先画好r颗珠子

然后在它们中间随便插入k-1块板子：

那么从左到右每一块板子之间就对应一种颜色：

那么这就是一种情况了

这就说明，每一种插板方案都对应了一种珠子颜色的情况，那么问题就变成我们有多少种插板方案？

注意几个细节：插在最左边是允许的，就表示没有珠子是第一种颜色，两块板插在同一个间隙也是被允许的，就表示没有珠子是这两块板之间所表示的那个颜色

那么插板方案数怎么计算呢，我们来看上面那个例子： 第一块板在插的时候有(r+1)种选法：

当我把第一块板插进去后，第二块板就多了一种选择，有(r+2)种选法了：

然而两块板交换位置是同一种情况，So，最后除个二得到最终答案

总结一下： 我们要在r个珠子中插入(k-1)块板

第一块板有(r+1)种选择，第二块板有(r+2)种选择，第三块板有(r+3)种选择……第(k-1)块板有(r+k-1)种选择，所以根据乘法原理算出当前的答案：(r+1)*(r+2)*\cdots*(r+k-1)=\frac{(r+k-1)!}{r!}

但是板的顺序是没有关系滴，So，我们还要出去(k-1)块板的全排列总数，于是我们得到了最终答案：

好的，不过现在我们还是不能解决最上面的那个东西，我们还需要学习一个东西：容斥原理

我来简单（真的很简单）地来讲一下：

现在我们有三个集合：A，B，C，它们的韦恩图（你不用知道这是什么，往下看就行了）长这样：

现在我们要求\left|A\cup B\cup C\right|

那么我们就先\left|A\right|+\left|B\right|+\left|C\right|，但是中间的部分的周围3块（黄色，粉色，深蓝色）我们连续算了两次，我们就再减掉\left|A\cap B\right|,\left|A\cap C\right|,\left|B\cap C\right|

中间的紫色部分开始时被我们加了3次，然后又被我们减掉3次，So，我们还要把它加回去

于是乎，我们就得到了最终答案：

如果我们把这个式子稍稍扩展一下的话，就得到了容斥原理：

设s_1,s_2\cdots s_n为有限合集，\left|s\right|表示集合s的大小 ，则：

终于我们可以正式开始解决开始的那个问题了！

为了防止大家忘记它，我把它写在下面：

现在有k堆珠子，每堆珠子颜色不同，第i堆珠子有n_i颗，现在我们从所有的珠子中取出r颗，问你这r颗珠子有多少种搭配？（与顺序无关）

现在，如果我们不考虑n_i，就是我们上面解决的那个问题，答案就是C_{k+r-1}^{k-1}

现在我们来考虑n_i的限制，显然上面的那些情况中有很多情况是不能满足的，那把它们减去就好了

那么不符合条件的情况是那些捏？

我们设集合s_i表示至少取了n_i+1个颜色为i的珠子的所有情况，也就是s_i集合中i这个颜色的珠子个数一定超了n_i这个限制（其他的颜色情况我们不管），那么这个s_i一定都是要被我们舍弃的情况

然后有没有发现所有要被我们舍去的情况有这么多：\left|\bigcup^{n}_{i=1}s_i\right|

所以最终答案就是：C_{k+r-1}^{k-1}-\left|\bigcup^{n}_{i=1}s_i\right|

我们先来看一下，对于每一个\left|s_i\right|怎么求？

（注意一下，每个s_i里的情况都是不合法的情况，我们在算这个\left|s_i\right|的时候都是没有n_i限制的）

首先我们要从所有的珠子中取出n_i+1颗颜色i的珠子，这样的话，无论剩下的珠子怎么选都可以保证我们取出来的情况是在集合s_i里面的

取完了n_i+1颗颜色i的珠子后，我们还要拿r-n_i-1颗，那么这个有多少种情况捏？

这是没有n_i限制的，有没有发现这就是上面我们已经讨论过的问题，我们的结论是：C_{k+r-1}^{k-1}

只不过现在的r是r-n_i-1，代入以后我们得到了\left|s_i\right|=C_{k+r-n_i-2}^{k-1}

那么我们试着再来求一求：\left|s_i \cap s_j \right|

也就是我们要先取出n_i+1颗颜色i的珠子，n_j+1颗颜色j的珠子，这样剩下的珠子就可以随便取了，那么我们还要取几颗呢？(r-n_i-n_j-2)颗，带回我们上面的那个结论，我们就得到了：\left|s_i \cap s_j \right|=C_{k+r-n_i-n_j-3}^{k-1}

相信大家一定发现了其中的规律，后面的情况我就不多说了，然后我们就可以使用容斥原理了！

然后我们就得到了（好好理解一下↓）：

So，最终答案：

打代码时要注意：

• 我们可以枚举x从0到2^k-1，我们把x换成二进制后，假设有num位是1，分别是第i_1,i_2,\cdots,i_{num}，我们就表示：

这样就可以保证我们扫到每一种情况了

• 我们要算C_b^a的话，就得用P_b^a乘上a!的逆元（逆元是什么？戳），别忘了一边乘，一边模

c++代码（CF451E）：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int ll p=1000000007;

int k;
ll r,n[25],inv[25];

ll pow(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if (b%2) ans=(ans*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return ans;
}

void get_inv(ll n,ll p){
    inv[1]=1;
    for (ll i=2;i<=n;i++){
        inv[i]=inv[p%i]*(p-p/i)%p;
    }
}

int C(ll y,ll x){
    if (y<0||x<0||y<x) return 0;
    y%=p;
    if (y==0 || x==0) return 1;
    ll ans=1;
    for (int i=0;i<x;i++){
        ans=1ll*ans*(y-i)%p;
    }
    for (int i=1;i<=x;i++){
        ans=1ll*ans*inv[i]%p;
    }
    return ans;
}

int main(){
    get_inv(20,p);
    scanf("%d%lld",&k,&r);
    ll ans=C(k+r-1,k-1);
    for (int i=1;i<=k;i++){
        scanf("%lld",&n[i]);
    }
    for (int x=1;x<1<<k;x++){
        ll t=k+r,num=0;
        for (int i=0;i<k;i++){
            if (x>>i & 1) num++,t-=n[i+1];
        }
        t-=num+1;
        if (num%2==1) ans=(ans-C(t,k-1))%p;
        else ans=(ans+C(t,k-1))%p;
    }
    printf("%lld",(ans+p)%p);
    return 0;
}

参考： 《算法竞赛进阶指南》 李煜东 著