容斥原理

· · 算法·理论

从基础容斥开始

从最简单的开始观察：

通过规律发现结果 \sum\limits_{S\subseteq U}(-1)^{|S|+1}F(S)。

但还是要深究一下为何是 (-1)^{|S|+1} ——

从本质上理解，给集合 S 一个容斥系数 f(|S|) ，我们要让一个拥有 |S|=n 个属性的集合只被算 1 次，可以得到：\sum\limits_{i=1}^{n}\binom{n}{i}f(i)=1，一个合理的构造就是 f(i)=(-1)^{i+1}。

一般化的容斥

容斥可以帮助我们数数，下面以“物品”为数数对象，具体可以是方案、路径、数字等等；“条件”作为属性、限制的统称。

假设有 n 个条件 A_1,...,A_n 和物品集合 S 。简单思考，我们应该考虑每一个物品应该的贡献，计数答案的形式往往是：\sum\limits_{i=1}^{n}\sum\limits_{x\in S}c(x,A_i)f(A_i) 。

其中 c(x,A_i) 表示物品 x 在 A_i 条件下的贡献，f(A_i) 表示 A_i 条件的容斥系数。

一般情况下每个物品在某个条件下的贡献是 0/1 。

因为题目中往往让我们计算 S 中满足条件 A_0 的物品数，而我们只能够求得一些限制较为宽松的条件 A_1,...,A_n 的物品数，我们设为 s(A_i) 。所以我们要通过容斥系数，让每个物品贡献到应该贡献的地方，即：s(A_0)=\sum\limits_{i=1}^{n}s(A_i)f(A_i) 。

这个容斥系数怎么求，也就是计数问题的重点。不同的问题有不同的解法，但还是有迹可循的。一定要抓住计数的对象是谁、条件是谁，搞清楚每一步已知什么、在求什么。

例 1

求有多少个长为 n 的排列 a_1,...,a_n 满足 a_i\neq i 。

也就是求恰好 0 个位置满足 a_i=i 的排列数。“恰好”的条件不好求，但是“至少”是好求的，至少 i 个位置满足 a_i=i 的排列数显然是 \binom{n}{i}(n-i)! 。

然后要计算容斥系数，考虑一个有 m 个位置满足 a_i=i 的排列的贡献：在“恰好 m 个位置满足 a_i=i ”条件中贡献为 [m=0] ，在“至少 i 个位置满足 a_i=i ， i\le m ”条件中贡献为 \binom{m}{i} 。

设 f_i 表示至少 i 个位置满足 a_i=i 条件的容斥系数，g_i 表示恰好 i 个位置满足 a_i=i 条件的答案贡献，可以得到 \sum\limits_{i=0}^{m}\binom{m}{i}f_i=g_m 。

在这里 g_m=[m=0] ，然后可以二项式反演求得 f_i，f_m=\sum\limits_{i=0}^{m}(-1)^{m-i}\binom{m}{i}g_i=(-1)^m 。

例 2

求 [1,n] 中能被 a_1,...,a_m 中的奇数个 数 整除 的数 个数。

首先枚举 \{a_i\} 的子集 S ，就容易得到至少被 |S| 个数整除的数的个数为 \lfloor\frac{n}{~lcm~ S}\rfloor 。

类似的思路，若有一个恰好能被 k 个 a_i 整除的数，它的贡献应该是 k~mod~2 ，所以得到容斥系数的计算式为 \sum\limits_{i=0}^{k}\binom{k}{i}f_i=k~mod~2 。

考虑到 m 很小，所以直接 O(m^2) 递推。递推式很好得到，首先 f_0=0 ，然后把 f_k 拆出来，f_k=(k~mod~2)-\sum\limits_{i=0}^{k-1}\binom{k}{i}f_i 。

总结

可以发现，我们先转化题目条件，求出若干较好满足的条件的答案，条件之间的转化常见的有：

然后往往是从一个物品应该的贡献出发，得到容斥系数的计算式，然后通过递推，或是递推打表后找规律，或是直接反演得到容斥系数。

对于很多数据范围很大的题目，容斥系数的计算式有一些很常见的形式，对应着一些基本的反演类型：