寒鸽儿のBlog

关于容斥原理的学习笔记

原理

公式(摘自OI-Wiki) :

设 U 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $P_i$ ，拥有属性$P_i$的元素构成集合 $S_i$ ，那么所有元素的并集大小为 :
$\displaystyle \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}^{m} S_{a_i} \right|$
若求交集，则利用全集减去补集的并集 :
$\displaystyle \left| \bigcap_{i=1}^{n} S_i \right| = \left| U \right| - \left| \bigcup_{i=1}^{n} \complement_U^{S_i} \right|$

感性理解 :

求并集，需要不断地把重复统计的元素减去。
全集减去补集的并的部分即为所有补集都没有的部分，换言之，时所有原集合共有的部分，即交集。

一般实现方法 :

通过枚举所有的选取方案求容斥，一种是利用二进制表示选取的方式，一种是用dfs。

1) dfs法

//借鉴jiangly神仙的代码改编
Number ans;
void dfs(int cur, int sign, Number valueState) {
	if(cur == n) {
		ans += valueState;
		return;
	}
	dfs(cur + 1, sign, valueState);    //不选
	dfs(cur + 1，-sign, valueState + calc(cur)); //选择
}

signed main() {
    ...
    dfs(0, 1, ...);
    ...
}

2) 二进制枚举

正在咕。。。

3) 数组模拟二进制

正在咕。。。

应用

正在咕。。。