基本容斥原理

目的:求n个集合的并

 

容斥原理的思想就是反过来算, 结论就是

至少覆盖一次的面积 - 至少覆盖两次的面积 + 至少覆盖三次的面积....

A + B + C - A∩B - A∩C - B∩C + A∩B∩C

 

至少覆盖y次的面积的计算方法: 暴力枚举所有的y个图形的组合,一共有C\binom{y}{n}种,求所有组合的面积交之和

恰好覆盖x次的面积  在  至少覆盖y次的面积 里面会被计算到C\binom{y}{x}次,相当于在x个集合里任意挑选y个集合都可以覆盖这块面积.

G(i) : 恰好覆盖i次的面积

F(i) : 覆盖次数大于等于i次的面积

G(x)F(y) 里面被算到的次数为C\binom{y}{x}

可以得到如下表格. 然后可以发现每一列错位加减之后,系数都会变成1,也就有了一开始的结论

\sum_{i=1}^n G(i)\sum_{i=1}^n F(i)*(-1)^{i+1}

 G(1)G(2)G(3)G(4)
F(1)C(1, 1)C(2, 1)C(3, 1)C(4, 1)
F(2)C(2, 2)C(3, 2)C(4, 2)
F(3)C(3, 3)C(4, 3)

如何用这个来做题呢?

只要发现G(x)比较难算,F(x)比较好算就可以尝试容斥,

但是在容斥之前要注意系数关系,即通过F(x)加加减减之后算出来的

G(i)的每一项系数都为1,才能利用容斥来做。简单的容斥如上面所述,

只要G(x)F(y) 里面被算到的次数为C\binom{y}{x} 就能直接大力的错位加减。

发表评论

电子邮件地址不会被公开。 必填项已用*标注