容斥
容斥原理
引入
首先，我们来看集合只有两个的情况。如果有集合 $A,B$，求 $|A\cup B|$，那么我们可以先将两个集合里面的元素数量加起来，然后再减去两个集合都有的元素，也就是 $|A\cup B| = |A|+|B|-|A\cap B|$。
然后，再看有三个的情况。对于集合 $A,B,C$，如果我们要求 $|A\cup B\cup C|$，那么显然就是三个集合内的元素个数加起来，再分别减去相交的，然后再加回来三个都相交的。即 $|A\cup B\cup C| = (|A|+|B|+|C|) - (|A\cap B| + |B\cap C| + |C\cap A|) + |A\cap B\cap C|$。
于是，我们不妨猜测结论有 $n$ 个集合 $S_i(i\in [1,n])$，则：
$$
\left |\bigcup_{i=1}^n S_i\right | = \sum_{i=1}^n(-1)^{i-1}\sum_{a_j\le a_{j-1}}\left |\bigcap_{j=1}^i S_{a_i} \right |
$$
其中，$\displaystyle \sum_{a_j\le a_{j+1}} \left |\bigcap_{j=1}^i S_{a_i} \right |$ 可以认为是在 $n$ 个集合选择 $i$ 个交起来的集合大小的和。而这一步最主要的目的便是将 $\bigcup$ 变成了一堆 $\bigcap$ 的和，当然我们需要加上容斥系数 $(-1)^{i-1}$。
证明
首先，我们假设有全集 $U$，于是显然地：
$$
\displaystyle\left |\bigcup\limits_{i=1}^n S_i \right|\Leftrightarrow \sum_{x\in U} \bigvee_{i=1}^n\left[x\in S_i\right]
$$
也就是说，所有出现在全集中的，且在 $S_1,\dots,S_n$ 中出现至少一次的会贡献一。于是，我们设元素 $x\in U$ 在 $S_{b_1},S_{b_2},\dots,S_{b_m}$ 中出现过，那么在式子 $\displaystyle \sum_{i=1}^n (-1)^{i-1}\sum_{a_j\le a_{j+1}}\left | \bigcap_{j=1}^m S_{a_j} \right |$ 中，它显然在序列 ${a_i}\sube {b_m}$ 时才会产生贡献，其中这贡献是 $(-1)^{i-1}$。于是，我们对于 $i\in [1,m]$ 分别考虑。对于任意一个 $i$，我们显然需要先从 $b_m$ 中选择 $i$ 个来生成这个 ${a_i}$，然后这些都会贡献 $(-1)^{i-1}$。那么，这元素就一共会产生
$$
\sum_{i=1}^m\binom{m}{i}(-1)^{i-1}
$$
的贡献。而这个式子不难证明等于 $1$。于是我们就证明了它的正确性。另外，这式子也可以用数学归纳法证明，这里不讲了。
上面我们探讨了如何将 $\bigcup$ 变成许多的 $\bigcap$，但是，如果我们希望求 $\bigcup$，而问题是求 $\bigcap$ 怎么办呢？
这其实也非常简单，我们可以借助另一个式子：
$$
\left |\bigcap_{i=1}^n S_i\right | = \left | U \right | - \left | \bigcup_{i=1}^n \overline{S_{a_i}} \right |
$$
其中 $\overline S$ 代表 $S$ 在 $U$ 意义下的补集。即 $\overline S = \complement _{U} S$。这个式子表明，交集的大小等于全集减去它们补集的并的大小。
应用
我们刚刚探讨了容斥的基本式子以及它们的推导，但是我们还并未探讨如何应用这些式子。
不定方程模型
而为了方便地继续探讨，我们在这里先引入一个例子：
例题
求不定方程 $\displaystyle \sum_{i=1}^n x_i = m$ 的非负整数解的个数。其中给出 $n$ 个限制，每个限制形如 $x_i\le b_i$。
容斥模型
在做题目的时候，我们需要注意找准以下三个要素：
- 全集，即 $U$，这里我们设所有的 $n$ 阶满足 $\sum\limits_{i=1}^n x_i = m$ 的行向量组成的集合为 $U$，即 $U={(x_1,x_2,\dots,x_n)\mid x_i\in\mathbb{N},\sum x_i = m,i\in[1,n]}$。
- 元素。这里虽然 $U$ 中的元素为行向量，但是，因为限制条件为 $x_i\le b_i$，所以这里元素选择 $x_i$。
- 属性。这里的属性是定义我们 $S_i$ 的关键。我们这里的属性就是题目中给出的性质 $x_i\le b_i$，而集合 $S_i$ 就表示为满足属性 $i$ 的解的数量，当然了，它还得满足条件 $\sum x_i = m$。即 $\left |S_i\right | = \sum\limits_{X\in U} [x_i\le b_i\wedge \sum x_i = m]$。
因为我们要满足所有的条件，所以我们要求的就是这些集合的交集，即 $\displaystyle\left | \bigcap_{i=1}^n S_i \right |$。
然后我们要找找自己会做什么。首先大家肯定会没有限制的时候，即 $\left | U \right | $。而这个问题就是典型的插板问题。这不定方程 $\sum x_i = m$ 就等价于给 $m$ 个苹果和互不相同的盘子，每个盘子可以为空，问有多少放的方法。直接插板即可，答案就是 $\displaystyle\binom{n+m-1}{n-1}$。
再然后，我们发现我们还会如果令 $x_i>b_i$ 的做法。显然，如果我们要让 $x_i>b_i$ 那么就先给 $x_i$ 分配 $b_i+1$ 个然后就可以随便分了。于是满足第 $a_1,a_2,\dots,a_k$ 个条件（这里的条件是限制的补集）的答案，这就相当于让我们解不定方程 $\sum x_i = m-\sum (b_{a_i}+1)$。答案即为 $\displaystyle\binom{m-\sum({b_{a_i}}+1)+n-1}{n-1}$。因为我们这是同时满足了一些限制的补集，也就是我们知道了 一些限制的补集的交的快速做法，也就是会了 $\displaystyle\bigcap \overline{S_{a_i}}$，而我们要求的是 $\displaystyle\bigcap_{i=1}^nS_i$，于是我们按照刚刚学习的那两个公式展开一下：
$$
\begin{aligned}
\left |\bigcap_{i=1}^n S_i \right |
&= \left | U \right | - \left | \bigcup_{i=1}^n \overline{S_i} \right |\
&= \left | U \right | - \sum_{k=1}^n (-1)^{i-1}\sum_{a_i\le a_{i+1}}\left | \bigcap_{i=1}^k \overline{S_{a_i}} \right |
\end{aligned}
$$
然后你就完全理解了。但是因为这里 $x_i$ 两两不同，所以需要 $2^n$ 求。
例题
HAOI2008 硬币购物
就和这个题完全一样，只是 $x_i$ 前加了系数 $c_i$，并无本质区别。
Code
1 |
|
小节
我们现在有两个公式：
- $\left |\bigcup\limits_{i=1}^n S_i\right | = \sum\limits_{k=1}^n(-1)^{k-1}\sum\limits_{a_i\le a_{i+1}}\left | \bigcap\limits_{i=1}^k S_{a_i} \right |$，它可以把 至少满足一个 的条件转化为 必须都满足 的条件。
- $\left | \bigcap\limits_{i=1}^n S_i \right | = \left | U \right | - \left | \bigcup\limits_{i=1}^n \overline{S_i} \right |$，它可以把 必须都满足 的条件转化为 至少满足一个。而这里条件要取反。
例题
JSOI2015 染色问题
Des
给定一个 $n\times m$ 的矩阵，每个格子上可以涂 $k$ 种颜色，要求：
- 每个颜色都必须用上。
- 每一行、每一列都至少要有一个格子涂了颜色。
求涂的方案数。模数。
Sol
首先，这里很显然有两个限制。我们先考虑第一个。
因为有限制 每个颜色必须使用，我们就设 $S_i$ 表示使用了 $i$ 颜色的方案数。于是我们要求的就是 $\left|\bigcap\limits_{i=1}^n S_i\right|$。然后，我们发现，我们会求 至少有 $k$ 个颜色不用 的情况下的颜色数量。因为至少有 $k$ 个颜色不用，换句话说，我们 钦定 $k$ 个颜色不能用，剩下的用不用都可以，这样的方案数我们设有 $f_{c-k}$ 个（$c$ 为颜色数量），也即 $f_i$ 表示最多使用 $i$ 个颜色且满足条件二的方案数。也即 $\left | \bigcap\limits_{i=1}^k \overline{S_{a_i}} \right | = f_{c-k}$。于是我们就对于答案进行了最初的转化：
$$
\begin{aligned}
\left | \bigcap_{i=1}^c S_i \right |
&= \left | U \right | - \left | \bigcup_{i=1}^c\overline{S_i} \right |\
&= \left | U \right | - \sum_{k=1}^c(-1)^{k-1}\sum_{a_i\le a_{i+1}}\left | \bigcap_{i=1}^k \overline{S_{a_i}} \right |\
&= \left | U \right | - \sum_{k=1}^c(-1)^{k-1}\binom{c}{k}f_{c-k}
\end{aligned}
$$
其中组合数 $\binom{c}{k}$ 是因为 $c$ 中颜色是一样的，故我们随便选择一组 $k$ 个即可。
于是问题就变成了求 $f_i$。这里我们再使用一次容斥，$S_i$ 表示 $i$ 列并没有空余的情况，于是我们要求的就是 $\left | \bigcap\limits_{i=1}^m S_i \right |$。然后我们考虑什么好做。发现如果我们 钦定 $k$ 列没有不涂颜色，我们可以轻松算出答案是 $((i+1)^{m-k}-1)^n$。其中 $i+1$ 代表了我们现在使用的颜色数量（加上空白的），而 $m-k$ 指的是 $m-k$ 列随便填，又因为每一行不能为空，所以要减去一种全空的情况，然后 $n$ 行互不相同，就在外面套一个 $n$ 次幂。而 $k$ 列为空代表的集合是 $\left | \bigcap\limits_{i=1}^k \overline{S_{a_i}} \right |$，然后再按照套路将要求的 $\left | \bigcap\limits_{i=1}^m S_i \right |$ 展开一下，就能够得到：
$$
f_i=((i+1)^m-1)^n - \sum_{k=1}^m (-1)^{k-1}\binom{m}{k}((i+1)^{m-k}-1)^n
$$
最后回带即可。
Code
1 |
|