容斥原理和二项式反演

不知道是哪位大佬说过的，容斥和反演本质上是一回事（本质上来说，是求解矩阵的逆，~~但是你观察后发现，这个矩阵实际上是一个三角矩阵，那必然存在着快捷的方法~~）不管是数论上还是组合上：莫比乌斯反演就是在因子多重集上的反演。——CommandBlock

容斥原理¶

说白了就是求并集转成求交集（交一般是好求的）

Note

在1到100的自然数中，既不是5的倍数也不是6的倍数的数有多少个？

解：从1到100的自然数中，减去5或6的倍数的个数（并集）。从1到100的自然数中，5的倍数有100÷5=20个，6的倍数有16个（100÷6= 16……4），其中（交集）既是5的倍数又是6的倍数（即5和6的公倍数）的数有3个（100÷30= 3……10）。因此，是6或5的倍数的个数是16＋20－3=33个，既不是5的倍数又不是6的倍数的数的个数是：100－33=67个。

思想¶

我们注意到，这个方法的基本思想是，先硬算，若有计数部分重复包含时，应从它们的和中排除重复部分。我们抽象一下：

假设有一堆物品集合 \(S\)，共有 \(|S|\) 个。一共有 \(n\) 个属性，所有的物品有零个或多个属性。假设能快速求包含任意某几个属性的物品个数，问无属性的物品有多少？

首先是无法直接计算无属性的物品的，因此考虑用总数减去所有有属性的物品。

钦定包含第 \(i\) 个属性物品的集合为 \(A_i\)，也就是我们知道了所有（至少）有某一个属性的集合，那么可以这么计算：

加上所有的 \(A_i\)，此时具有 \(\gt 1\) 个属性的物品一定会算重；
把 \(A_i\) 两两求交，得到所有（至少）有某两个属性的集合，尝试减去所有的新集合，此时具有 \(\gt 2\) 个属性的物品会被减多；
再把 \(A_i\) 三个三个求交，得到所有（至少）有某三个属性的集合，加上所有的新集合，此时具有 \(\gt 3\) 个属性的物品会被算重；
……
由于最多只有 \(n\) 个属性，因此最后就是 \(n\) 个 \(A_i\) 求交，加减一下，此时由于不存在 \(\gt n\) 个属性的物品，不会算重。

归纳一下，设 \(T\) 是 \(n\) 个属性的任意子集，则有：

\[ \left | \bigcup_{i=1}^nA_i \right |=\sum_{T\subseteq \{1,2,...,n\}}(-1)^{|T|-1}\left | \bigcap_{i\in T} A_i \right | \]

求无属性的物品个数，我们可以用全集大小-有属性物品得到，即下面的补集转换：

\[ \left|\bigcap_{i=1}^n \overline{A_i}\right|=|S|-\left|\bigcup_{i=1}^n A_i\right| \]

由德摩根定律，我们有交集转化成补集的并：

\[ \left|\bigcap_{i=1}^n A_i\right|=|S|-\left|\bigcup_{i=1}^n \overline{A_i}\right| \]

这里埋个伏笔，我们本质上算的是属性个数恰好等于0的个数。

例题¶

毒瘤选举

毒瘤选举大会有 \(n\) 位选民和 \(k\) 位候选人。选民不会弃权或投多票。一位候选人是毒瘤的当且仅当至少有一名选民给他投票。

现在，Magolor想知道在所有的投票方案中，有多少种方案满足所有候选人都是毒瘤的。因为方案数特别多，Magolor只需要你输出答案 mod 998244363

考虑到所有人都毒瘤是个比较严的限制，我们正难则反，也就是求所有投票方案-存在候选人不毒瘤。（补集转化的式子）

我们注意到存在候选人不毒瘤本质上是个并，即我们可以求：钦定哪几个人不毒瘤，剩下的随意的方案。然后套用上面的公式即可。

假设钦定 \(m\) 个人不毒瘤（即至少有 \(m\) 个人不毒瘤）：\(\binom{k}{m}(k-m)^n\)

最终答案为：\(k^n-\sum_{i=1}^m(-1)^i\binom{k}{i}(k-i)^n\)

整数划分

求出 \(n\) 个正整数和为 \(s\) 的方案数
求出 \(n\) 个自然数和为 \(s\) 的方案数
求出 \(n\) 个 \([1,x]\) 的数和为 \(s\) 的方案数
求出 \(n\) 个 \([0,x]\) 的数和为 \(s\) 的方案数
求出 \(n\) 个 \([a,b]\) 的数和为 \(s\) 的方案数

简单计数，考虑划分 \(s\) 个 \(1\) 为 \(n\) 份，插板法有 \(\binom{s-1}{n-1}\)
令所有数加一，即变为求出 \(n\) 个正整数和为 \(s+n\) 的方案数，插板法有 \(\binom{s+n-1}{n-1}\)

后面几个容斥，由于满足 \(\leq x\) 约束的方案不好计算，正难则反，我们在 \(n\) 个数中钦定 \(i\) 个不符合条件，即预先给 \(i\) 个数拿掉 \(x\)，剩下的插板。

\[ \sum_{i=0}^n (-1)^i\dbinom{n}{i}\dbinom{s-ix-1}{n-1} \]

其余同理，平移一下取值范围即可。

广义容斥原理（二项式反演）¶

用于至少/至多是这个集合到恰好是某个集合和切换。至少和至多还是有点抽象，其实是：在这个子集中钦定子集（至多）、钦定这个子集必选+别的随意（至少）。很多题要先钦定好，才容易列式子二项式反演，最终求出恰好是的那个集合。

沿用上面的抽象，如果要求恰好有 \(k\) 个属性的物品有多少个，阁下又该如何应对呢？

我们一路上的计算全是至少有 \(i\) 个属性的物品，并不能直接算出恰好。

二项式反演¶

至少转恰好¶

记 \(f_k\) 表示恰好有 \(k\) 个属性的方案数，\(g_k\) 表示所有属性中钦定 \(k \leq i \leq n\) 个属性的总方案数和，即：

\[ g_{k}=\sum\limits^{n}_{i=k}\binom{i}{k}f_{i} \Leftrightarrow f_{k}=\sum\limits^{n}_{i=k}(-1)^{i-k}\binom{i}{k}g_{i} \]

这个也就是问题的答案——恰好有 \(k\) 个属性的物品集合大小 \(f_k\) 和至少有 \(k\) 个属性的物品集合大小 \(g_k\) 之间的关系。如果不太好理解，求 \(f_0\) 即为容斥原理。（证明看链接）

集合计数

一个有N个元素的集合有 \(2^N\) 个不同子集（包含空集），现在要在这 \(2^N\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数恰好为K，求取法的方案数，答案模1000000007。

（有某个元素就是有某个属性）

如何求交集元素至少为 \(i\) ？从所有元素钦定选 \(i\) 个元素构成交集，有 \(\binom{n}{i}\) 种方案。剩下的元素可以组成 \(2^{n-i}\) 个子集，每个子集可选可不选，就有 \(2^{2^{n-i}}\) 种方案。答案：

\[ f_{k}=\sum\limits^{n}_{i=k}(-1)^{i-k}\binom{i}{k}\binom{n}{i} 2^{2^{n-i}} \]

至多转恰好¶

记 \(f_k\) 表示恰好有 \(k\) 个属性的方案数，\(g_k\) 表示所有属性中钦定 \(0 \leq i \leq k\) 个属性的总方案数和，即：（这里一般上界 \(n=k\)）

\[ g_{k}=\sum\limits^{k}_{i=0}\binom{k}{i}f_{i} \Leftrightarrow f_{k}=\sum\limits^{k}_{i=0}(-1)^{k-i}\binom{k}{i}g_{i} \]

子集反演¶

放个公式，二项式反演是从这里来的（也许？）

至多转恰好¶

\[ g(S)=\sum_{T\subseteq S}f(T)\Leftrightarrow f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T) \]

至少转恰好¶

\[ g(S)=\sum_{S\subseteq T}f(T)\Leftrightarrow f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T) \]

链接¶

『容斥原理和广义容斥原理』 - Parsnip - 博客园（二项式反演的详细证明）

浅谈容斥原理 - Quick_Kk - 博客园（例题较多）

反演魔术：反演原理及二项式反演 | Miskcoo’s Space

炫酷反演魔术 - command_block 的博客 - 洛谷博客

子集反演学习笔记 - Pbri - 博客园