「数学」基础容斥学习笔记

容斥的定义

公式

对于一个 有限集 A ,有

\left| \bigcup _ { i = 1 } ^ { n } A _ { i } \right| = \sum _ { i = 1 } ^ { n } \left| A _ { i } \right| - \sum _ { 1 \leqslant i < j \leqslant n } \left| A _ { i } \cap A _ { j } \right| + \sum _ { 1 \leqslant i < j < k \leqslant n } \left| A _ { i } \cap A _ { j } \cap A _ { k } \right| - \cdots + ( - 1 ) ^ { n - 1 } \left| A _ { 1 } \cap \cdots \cap A _ { n } \right|

也可以写成

\left| \bigcup _ { i = 1 } ^ { n } A _ { i } \right| = \sum _ { \emptyset \neq J \subseteq \{ 1,2 , \ldots , n \} } ( - 1 ) ^ { | J | - 1 } \left| \bigcap _ { j \in J } A _ { j } \right|

其中 |A| 表示 A 基数 (即集合中包含的元素的「个数」)。例如在两个集的情况时,我们可以通过将 |A| |B| 相加,再减去其交集的基数,而得到其并集的基数

其他应用

g ( A ) = \sum _ { S : S \subseteq A } f ( S )

那么就有

f ( A ) = \sum _ { S : S \subseteq A } ( - 1 ) ^ { | A | - | S | } g ( S )

上面就是子集反演的形式....

例题

已知 n=\prod_{i=1}^{k}p_i^{c_i} , 求 \varphi(n)

直接上容斥即可

\begin{align} \varphi ( n ) &= n - \sum _ { i = 1 } ^ { k } \frac { n } { p _ { i } } + \sum _ { 1 \leqslant i < j \leqslant k } \frac { n } { p _ { i } p _ { j } } - \cdots \\&= n \prod _ { i = 1 } ^ { k } \left( 1 - \frac { 1 } { p _ { i } } \right) \end{align}

求把大小为 n 的集合分为 k 个非空子集的方案数 (第二类斯特林数)

考虑容斥

\left\{ \begin{array} { l } { n } \\ { k } \end{array} \right\} = \frac { 1 } { k ! } \sum _ { i = 0 } ^ { k } ( - 1 ) ^ { i } \left( \begin{array} { l } { k } \\ { i } \end{array} \right) ( k - i ) ^ { n }


对于容斥原理的题目,都有一个通用的套路

  1. 首先将题目中的 n 个限制列出来
  2. 枚举限制的 2^n 个子集
  3. 对于每个子集 S 计算出不满足子集中条件的个数 k
  4. |S| 为奇数,那么 \text{ans} 就减去 k ,否则 \text{ans} 就加上 k

Min-Max 容斥

定义对于集合 S 的运算 \max(S) p_1,p_2\cdots p_k\in S, \max(S)=\max(p_1, p_2, \cdots, p_k)

\max ( S ) = \sum _ { \varnothing \neq T \subseteq S } ( - 1 ) ^ { | T | - 1 } \min ( T )

具体证明使用二项式反演证明

例题:

TopCoder-14766 TestProctoring

现在有 n 个学生,每个学生在每一秒都有一个概率,表示该学生在该时刻考完试的概率。现在需要求所有学生考完试所需要的期望时间。

直接算,不会期望请参考上一篇博客

X_i 表示第 i 个学生考完试的时间,那么就转化为了求 E(\max(X_1, X_2, \cdots , X_n))

由于期望线性性及 \text{Min-Max} 容斥,可以得到

\begin{align} E(\max(X_1, X_2, \cdots , X_n)) &= E(\sum_{\emptyset \neq T \subseteq S}(-1)^{|T|-1}\times \min(T))\\&= \sum_{\emptyset \neq T \subseteq S}E((-1)^{|T|-1}\times \min(T))\\&=\sum_{\emptyset \neq T \subseteq S}(-1)^{|T|-1}E(\min(T)) \end{align}

所以就转化为求 E(\min (T)) 了,也就是期望第一个学生考完试的期望时间

考虑 T 中的学生第 i 时刻有人考完试的概率 P_T ,有

P_T=1-\prod_{i\in T}\left(1-{1\over p}\right)

所以说它的期望就是 1\over P_T

代码比较 naive,就不放了。(实际上把下面那题的代码改改就能过)

HDU4336

链接: 这里

n 个卡牌,每秒有 p_i 的概率抽到卡牌 i ,求至少得到每个卡牌至少一张的期望时间 E(t)


X_i 为获得第 i 张牌的时间,那么题目中就是求 E(\max(X_1,X_2, \cdots, X_n)) ,这就是 \text{Min-Max} 容斥的形式,我们将它写出来:

\max ( X ) = \sum _ { \emptyset \neq T \subseteq S } ( - 1 ) ^ { | T | - 1 } \min ( T )

注意到对于 \min(S) 相当于 第一次 抽到卡牌的时间,所以

E(\min(S))={1\over \sum_{i\in S}p_i}

然后代码就很简单:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

static const bool ParityTable256[256] = {
#define P2(n) n, n^1, n^1, n
#define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
P6(0), P6(1), P6(1), P6(0)
};

const int MAXN = 20 + 5;

double bit[MAXN];

inline double split (unsigned int S) {
double ret = 0;
for (unsigned int i = 0; i <= 20 && (S >= (1 << i)); i++){
if (S & (1 << i)) ret += bit[i];
// printf("[DEBUG]i = %d, i << %d = %d, bit[%d] = %d\n", i, i, 1 << i, i, bit[i]);
}
return ret;
}

int main (int argc, char *const argv[]) {
int n;
while (~scanf("%d", &n)) {
for (int i = 0; i <= n - 1; i++) std::cin >> bit[i];
double ans = 0;
for (unsigned int i = 1; i < (1 << n); i++) { // 另一种枚举子集
unsigned char *p = (unsigned char *) &i;
double cnt = (ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]]) ? 1.0 : -1.0;
// 上面是判断二进制位中 1 个数的奇偶性
// 不过我可能写麻烦了 (?)

// printf("[DEBUG]cnt = %lf, split(%d) = %lf\n", cnt, i, split(i));
ans += cnt / split(i);
}
printf("%.4lf\n", ans);
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!