容斥原理解决的往往是一类求若干集合的并集问题,且一般都是易求交集,难求并集。其思想的核心正是把对集合的 or 操作都转化为 and 操作。
规定一些记号:用大写字母表示一个集合, A∩B 表示 A 与 B 的交集, A∪B 表示 A 与 B 的并集。
下面就举一例具体分析容斥原理。
在 n 以内的自然数中,能被 3 整除或能被 5 整除的数有多少个?
用 O(n) 枚举当然很容易,但是用学好数学,用容斥原理,可以做到 O(1)!
首先考虑能被 3 整除的数组成的集合 A,显然有
|A|=⌊n÷3⌋
同理,对于能被 5 整除的数组成的集合 B,有
|B|=⌊n÷5⌋
正如上面的维恩图所示,我们所得到的 A 与 B 实际上是有交集的。如果单纯地把 |A|+|B| 作为答案,就会出错,例如 15,作为 3 的倍数被考虑过一次,作为 5 的倍数的时候又被考虑,就会计多了一次。不难发现,凡是被多计一次的,都同时满足是 3 的倍数和是 5 的倍数,即 A 与 B 的交集 C 实际上就是 15 的倍数。
既然多加了,那么只要把这部分减去即可,即最终的答案
|D|=|A|+|B|−|C|=|A|+|B|−|A∩B|
设有 A,B,C三个集合,这三个集合相互均有交集,并且三个集合之间也有交集。则这三个集合的并集可以表示为
A∪B∪C=A+B+C−A∩B−B∩C−A∩C+A∩B∩C
可以利用下面的图得到一个更为直观的解释:
在求两个集合的并集的时候,只需考虑减去中间重复计数的一小部分,即它们的交集。但在三个集合中,如果同样为了避免重复计数而减去三个集合之间两两的交集,就会发现,三个集合共同的交集被多减去了一次,因此要加回去。
除了上面这个问题外,其实还有一个我们常用的东西用到了容斥原理的思想,那就是二维前缀和。
如上图,预处理出左上角到每一个 (i,j) 的二维前缀和 f[i][j] 之后,为了求蓝色部分 (2,2) 到 (4,4) 的和,先取 f[4][4],发现有些部分是我们不需要的,就把红色部分的 f[4][1] 和黄色部分的 f[1][4] 减去,但这会导致左上角被多减了一遍,再加回去就是了。
利用这个原理不难推出满足普遍规律的式子。一般地,有
Sum(x1,y1,x2,y2)=f[x2][y2]−f[x1−1][y2]−f[x2][y1−1]+f[x1−1][y1−1]
关于容斥原理的证明,我不会严格的表达,但在这里大致记录一下思路:用数学归纳法证明。
对于两个集合的情况,显然是成立的。
只要对于 i 个集合的情况成立,就可以推出 i+1 个集合的情况也成立,由此可以推出所有情况都是成立的。
例如,在 A∪B∪C 中,可以将 A∪B 视作一个整体,那么有
A∪B∪C=(A∪B)∪C=(A∪B)+C−(A∪B)∩C=(A+B−A∩B)+C−[(A∩C)∪(B∩C)]=A+B−A∩B+C−(A∩C+B∩C−A∩B∩C)=A+B+C−A∩B−A∩C−B∩C+A∩B∩C
这样就可以证明容斥原理的正确性了。
总结一下,可以发现计算规律:把所有集合相加,同时减去所有偶数重复,加上所有奇数重复。简单来记忆就是减偶加奇。具体编程实现,要通过题目来说明。
容斥原理看似只是一堆加加减减的操作,但其实在实际应用中还是有一定的思维难度。如何不重复、不遗漏地求出具有若干属性的值,也是一门艺术。