容斥的思想贯穿了几乎所有的反演等…
它的重(du)要(liu)可见一斑

这里自行脑补一个Veen图吧 (

基本公式

  • 已知A_1,A_2,A_3… A_nA_1 \bigcup A_2 \bigcup…\bigcup A_n

给出公式:

A_1 \bigcup A_2 \bigcup…\bigcup A_n

|\bigcup_{i=1}^nA_i| = \sum_{k=1}^n (-1) ^{k-1} \sum _i|A_{i_1} \cap A_{i_2}\cap…\cap A_{i_k}|

一般情况下,A_i 代表了某些限制,我们要求的则是满足所有这些限制的方案数

因为上式的A意义类似于Venn图中的面积, 而事实上我们也可以看成是方案数!

个人理解

  • {A_n}在题目中的具体化表现?

    A : 多数为方案数

  • 为什么容斥式子好像很简单啊

    A : 相当于是在枚举违背限制的集合啊 (

我们显然有

[S=\empty]=\sum_{s\subseteq S}(-1)^{|s|}
那么假设题目中的限制条件组成的集合为S

对于某一个方案b, 设它的违反条件的集合为D(b)

那么显然有\text{总方案=} \sum_b [D(b)=\empty]

进一步化简:

\sum_b[D(b)=\empty]\\ =\sum_b\sum_{s\subseteq D(b)}(-1)^{|s|}\\ =\sum_{s\subseteq S} (-1)^{|s|} \cdot d(s)

d(x) 表示至少违反了x这么多限制的方案数!

那么这样一来就变成要求d(x)了, 就比较的好求了!

  • 如果我们求A的交呢?
    A: 那么…转化成A补集的并, 再取一下补集就是答案了吧…

Leave a Reply