容斥的定义

公式

对于一个 有限集 $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 }$

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

首先将题目中的 $n$ 个限制列出来
枚举限制的 $2^n$ 个子集
对于每个子集 $S$ 计算出不满足子集中条件的个数 $k$
若 $|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:

#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;
}

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

容斥的定义

公式

其他应用

例题

Min-Max 容斥

TopCoder-14766 TestProctoring

HDU4336