跳转至

容斥原理

假设班里有 10 个学生喜欢数学, 15 个学生喜欢语文, 21 个学生喜欢编程,班里至少喜欢一门学科的有多少个学生呢?是 10+15+21=46 个吗?不是的,因为有些学生可能同时喜欢数学和语文,或者语文和编程,甚至还有可能三者都喜欢。为了叙述方便,我们把喜欢语文、数学、编程的学生集合分别用 A,B,C 表示,则学生总数等于 |A\cup B\cup C| 。刚才已经讲过,如果把这三个集合的元素个数 |A|,|B|,|C| 直接加起来,会有一些元素重复统计了,因此需要扣掉 |A\cap B|,|B\cap C|,|C\cap A| ,但这样一来,又有一小部分多扣了,需要加回来,即 |A\cap B\cap C| 。即

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|

一般地,对于任意多个集合,我们都可以列出这样一个等式,等式左边是所有集合的并的元素个数,右边是这些集合的各种搭配。每个搭配都是若干个集合的交集,且每一项前面的正负号取决于集合的个数————奇数个集合为正,偶数个集合为负。即

S 为有限集, A_i\in S~(i=1,2,...,n~,~n\ge 2) ,则有

| \bigcup_{i=1}^n A_i | =\sum_{k=1}^n (-1)^{(k-1)} \times \sum_{1\le i_1<i_2<...<i_k\le n} |A_{i_1}\cap A_{i_2} \cap ...\cap A_{i_k}|

容斥原理在算法竞赛中的应用

例题 BZOJ 1042 [HAOI2008] 硬币购物

题目大意:一共有 4 种硬币,面值分别为 c_1,c_2,c_3,c_4 。某人去买东西,去了 tot 次。每次给出 d1,d2,d3,d4 d_i 表示有 i 个面值为 c_i 的硬币,求购买价值为 s 的物品的付款方案数。

先用多重背包预处理出 f(i) ,表示不限制钞票数量购买价格为 i 的物品的方案数。由于容斥原理,我们最后的答案为

f(s)-f(s-d_1)-f(s-d_2)-f(s-d_3)-f(s-d_4)

+f(s-d_1-d_2)+f(s-d_1-d_3)+f(s-d_1-d_4)+f(s-d_2-d_3)+f(s-d_2-d_4)+f(s-d_3-d_4)

-f(s-d_1-d_2-d_3)-f(s-d_1-d_2-d_4)-f(s-d_1-d_3-d_4)-f(s-d_2-d_3-d_4)+f(s-d_1-d_2-d_3-d_4)

这样,我们就可以在 O(1) 的时间复杂度内处理每个询问。

练习

BZOJ 4665 小 w 的喜糖

BZOJ 4361 isn


评论