容斥原理

$|\bigcup_{i=1}^nA_i|=\sum_{S\subseteq \{1,\dots,n\},S\neq \varnothing} |\bigcap_{i\in S}A_i|(-1)^{|S|-1}$ $\bigcap_{i=1}^{n}A_i=\sum_{S\subseteq\{1,\dots ,n\}}(-1)^{|S|}|\overline{\bigcup_{i\in S} A_i}|$

其中，我们认为全集 $U={1,\dots, m}$ 当中每一个元素都代表着一个事件（或者用计数题的专有名词，方案）。$m$ 是所有方案的个数。

方案是容斥原理当中的最小单位，它并不类似于期望，是不可分割的。

而 $A_i$ 表示满足条件 $p_i$ 的所有方案构成的集合，$p_i$ 是题目给定的一个限制。

那么原理一可以表述为：所有限制中至少满足一个可以转化为求所有非空限制子集全部满足。

原理二可以表述为：所有限制必须满足可以转化为求所有限制子集都不满足。

这两个东西的本质是 $\sum_{i=0}^n\binom{n}{i}(-1)^i=[n=0]$ 作用到集合当中所有元素的形式。

子集反演

$f(S)=\sum_{T\subseteq S} g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S} f(S)(-1)^{|S|-|T|}$ $f(S)=\sum_{S\subseteq T\subseteq N} g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S\subseteq N} f(S)(-1)^{|S|-|T|}$

其中 $N$ 表示所有限制构成的集合的全集。

这里我们认为 $S,T$ 均为限制集合。

我们不妨认为 $g(S)$ 表示 $S$ 里面的限制必须恰好满足的方案数。也就是

$g(S)=|(\bigcap_{i\in S}A_i)\cap (\bigcap_{i\notin S}\overline A_i)|$

一个显然的性质是，每个 $g$ 所代表的集合是不交的。并且这些集合并起来等于全集（每个方案属于唯一的 $g$）。

于是我们可以得到，$f$ 就应该表示所有只包含 $S$ 的子集而一定不包括外界其它方案的集合。也就是我们所谓钦定 $N-S$ 不选。

同理，底下那个就是钦定只选 $S$。

容易发现，原理二就是反演一右式在 $S=N$ 时的等价形式，我们也因此可以得到反演一中 $f$ 的数学含义。

$f(S)=|\bigcap_{i\in N-S}\overline {A_i}|$

也就是钦定不选。

那么考虑原理二，这个超集的形式稍微怪一点，但是这并不妨碍我们把它的数学含义直接推导出来。

$f(S)=|\bigcap_{i\in S}A_i|$

也就是钦定选。

证明依然可以考虑单个事件的去向。

于是我们得到了子集反演，一个用来处理恰好选问题的强大武器。

二项式反演

二项式反演是子集反演的压缩形式。

我们令 $F,G$ 分别代表自己反演的 $f,g$，那么我们定义新的 $f(n)=\sum{|S|=n}F(S)$ 以及 $g(n)=\sum{|S|=n}G(S)$

那么根据子集反演可以得到：

$F(S)=\sum_{S\subseteq T} G(T)\Longleftrightarrow G(S)=\sum_{S\subseteq T}(-1)^{|T-S|}F(T)$

两边取 $\sum$ 可以得到：

左式：

$f(m)=\sum_{|S|=m}\sum_{S\subseteq T}G(T)=\sum_{m\le |T|\le n}G(T)\sum_{|S|=m,S\subseteq T} 1=\sum_{i=m}^n\binom{i}{m}g(i)$

右式同理有：

$g(m)=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}f(i)$

于是我们得到了 $f,g$ 的关系。

$f(m)=\sum_{i=m}^n\binom{i}{m}g(i)\Longleftrightarrow g(m)=\sum_{i=m}^n\binom{i}{m}(-1)^{i-m}f(i)$

其中 $f$ 表示钦定任意选择 $m$ 个限制满足的所有方案，$g$ 表示实际上有 $m$ 个限制满足的所有方案。

再考虑另外一个子集反演的柿子，这个柿子和上一个柿子有些类似于 OGF 和 EGF 的关系，这个柿子要求题目中的 $n$ 个限制地位相同，然后可以使用。

令 $f(n)$ 表示我至多满足其中 $n$ 个方案的方案数，$g(n)$ 表示我恰好满足其中 $n$ 个方案的方案数。注意这里的“至多”和“恰好”真的是字面意思，因为你所有的限制都地位相同，用这两个词表述无疑是最合适的。

二者满足关系式：

$f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\Longleftrightarrow g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)$

[Luogu P6596] How Many of Them

求 $n$ 个点的带标号无向连通图中有多少个的割边数不大于 $m$。

$n,m\le 10^3$

这个东西是不好做的，考虑容斥，限制是每条边是/不是割边，显然每个边是等价的，因此任意一组边满足的数量也是相等的。

令 $ans(n)$ 表示割边至多 $n$ 个的方案数，令 $eq(n)$ 表示我恰好选了 $n$ 个的方案数，令 $sol(n)$ 表示我任意钦定其中的 $n$ 个割边的方案数。

我们求出 $sol(n)$，然后可以知道 $eq(n)$，再求出 $ans(n)$ 就可以了。

你以为这是两个二项式反演？错了！ $eq(n)$ 到 $ans(n)$ 是简单加和而并非二项式反演。

因为 $eq(n)$ 本身就包含了 $\binom{n}{i}$ 这一项，所以当然不需要二项式反演。

容斥系数的推导

[COCI 2009-2010 #6] XOR

给出 $(x,y,r)$ 描述的若干等腰直角三角形，顶点落在 $(x,y),(x+r,y),(x,y+r)$，一个合法的面积是有奇数个等腰直角三角形覆盖的面积。求所有合法面积并。

$n\le 10$

考虑容斥原理。

思考一下容斥原理/反演的本质，我们用一个已知的函数 $f$ 去表示一个未知的函数 $g$，这两个函数之间存在一定的联系。多数情况下这种关系是显然的，例如二项式反演，莫比乌斯反演。但是此时这里并没有那么显然的关系，需要我们自己构造一个函数 $f$。

考虑 $f(S)$ 表示 $S$ 子集当中所有三角形的面积交，这个状态的好处在于它一定可以通过一些方式推到 $g$ 表示的合法面积。

考虑 $g = \sum_{S}\alpha (S)f(S)$，那么我们就只需要求出 $\alpha(S)$ 这个函数就好了。

考虑一块面积， $S$ 是覆盖它的三角形集合。

我们希望 $\sum_{T\subseteq S,T\ne \emptyset}\alpha(T)=[|S|\ is\ odd]$。

显然我们希望大小相等的 $\alpha$ 是相同的。

$\sum_{i=1}^{|S|}\binom{|S|}{i}\alpha(i)=[|S|\bmod 2=1]$

那你是不是可以递推了。

$\alpha(n)=[n\bmod 2=1]-\sum_{i=1}^{n-1}\binom{n}{i}\alpha(i)$

小结论，$[n\bmod 2=1]\Leftrightarrow \frac {(-1)^{n-1}+1} 2$

打表找规律，发现 $\alpha(n)=(-2)^{n-1}$，代入可以检验。

tyy：这柿子不是闭着眼推么。

考虑 EGF，不妨令 $\alpha(0)=0$，我们有：

$e^xA=\frac {e^x-e^{-x}} 2$

于是

$A=\frac {1 - e^{-2x}} 2$

于是 $(-1)^{i+1}2^{i-1}$ 就是一个合法的 $\alpha$。也就是 $(-2)^{i-1}$。

于是接下来我们只需要枚举选多少三角形，求它们交的面积和乘上 $\alpha$ 即可。

直接暴力就行了。