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

超链接：[数学合集](https://blog.csdn.net/HenryYang2018/article/details/89399986) --- 打完这篇文章的数学公式真的要吐血身亡了…… --- 模板题：[CF451E](https://www.luogu.org/problemnew/show/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)块板的全排列总数，于是我们得到了最终答案： $$\frac{(r+k-1)!}{r!(k-1)!}=C_{k+r-1}^r=C_{k+r-1}^{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，我们还要把它加回去 于是乎，我们就得到了最终答案： $$\left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|A\cap C\right|-\left|B\cap C\right|+\left|A\cap B\cap C\right|$$ 如果我们把这个式子稍稍扩展一下的话，就得到了容斥原理： 设$s_1,s_2\cdots s_n$为有限合集，$\left|s\right|$表示集合s的大小 ，则： $$\left|\bigcup^{n}_{i=1}s_i\right|=\sum^n_{i=1}\left|s_i\right|-\sum_{1\leq i< j\leq n}\left|s_i \cap s_j \right|+\sum_{1\leq i< j< k\leq n}\left|s_i \cap s_j \cap s_k\right| +\cdots+(-1)^{n+1}\left|s_1\cap\cdots\cap s_n\right|$$ --- 终于我们可以正式开始解决开始的那个问题了！ 为了防止大家忘记它，我把它写在下面： **现在有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}$ 相信大家一定发现了其中的规律，后面的情况我就不多说了，然后我们就可以使用**容斥原理**了！ 然后我们就得到了（好好理解一下↓）： $$\left|\bigcup^k_{i=1}s_i\right|=\sum^k_{i=1}C_{k+r-n_i-2}^{k-1}-\sum_{1\leq i< j\leq n}C_{k+r-n_i-n_j-3}^{k-1}+\cdots+(-1)^{k+1}C_{k+r-\sum_{i=1}^kn_i-(k+1)}^{k-1}$$ So，最终答案： $C_{k+r-1}^{k-1}-\sum^k_{i=1}C_{k+r-n_i-2}^{k-1}+\sum_{1\leq i< j\leq n}C_{k+r-n_i-n_j-3}^{k-1}-\cdots+(-1)^kC_{k+r-\sum_{i=1}^kn_i-(k+1)}^{k-1}$ --- 打代码时要注意： - 我们可以枚举x从0到$2^k-1$，我们把x换成二进制后，假设有num位是1，分别是第$i_1,i_2,\cdots,i_{num}$，我们就表示： $(-1)^{num}C_{k+r-n_{i_1}-n_{i_2}-\cdots -n_{i_p}-(num+1)}^{k-1} $ 这样就可以保证我们扫到每一种情况了 - 我们要算$C_b^a$的话，就得用$P_b^a$乘上a!的逆元（逆元是什么？[戳](https://blog.csdn.net/HenryYang2018/article/details/89372739)），别忘了一边乘，一边模 --- c++代码（CF451E）： ```cpp #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; } ``` 参考： 《算法竞赛进阶指南》 李煜东 著