容斥原理

概述

容斥原理是非常重要的计数原理：

$$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|$$

集合的交集可以使用补集容斥原理来求解：

$$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$$

容斥原理最经典的用处是“至少”与“恰好”之间的转化，实际上是一个子集反演的过程。子集反演是针对集合交并的容斥，可以在恰好是某个集合和至多/至少是这个集合反演。

我们先来看与至多是这个集合的反演。现在有其元素满足某种条件的集合 $A$。定义 $f(S)$ 代表 $S=A$ 时的答案，$g(S)$ 代表 $S\subseteq A$ 时的答案。

钦定选了 $S$ 这个集合中的子集 $T$，有 $g(S)=\sum_{T\subseteq S}f(T)$，这时有 $f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)$。使用容斥原理不难感性理解。

类似的，如果 $f(S)$ 代表 $S=A$ 时的答案，$g(S)$ 表示 $A\subseteq S$ 时的答案，有 $g(S)=\sum_{S\subseteq T}f(T)$，反演得 $f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T)$。

这是容斥原理的代数形式，它是我们用容斥原理解决问题的基础。因为在钦定时，一个“有两个元素满足条件”的东西会在“至少有一个元素满足条件”的东西计算时计算两次，也就因此成了一个子集反演的形式。