主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
浅谈 min-max 容斥
最后更新于 2025-07-31 09:33:17
作者
ZYStream
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
# min-max 容斥 对于一个长度为 $n$ 数列 $\left \{ a_i \right \}$,有如下式子: $$ \max_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \min_{j \in T} \left \{ a_{j} \right \} $$ $$ \min_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \} }(-1)^{\left | T \right | -1} \max_{j \in T} \left \{ a_{j} \right \} $$ 以上计算过程称作 min-max 容斥,也叫最值反演,证明过程参考的 [OI Wiki](http://oi-wiki.com/math/combinatorics/inclusion-exclusion-principle/#min-max-%E5%AE%B9%E6%96%A5),把该计算过程用一般的容斥原理表示出来即可证明,考虑构造双射 $f(x)=\left \{ 1,2,\cdots ,x \right \}$,显然 $x=\left | f(x)\right |$,$\min \left \{ x,y\right \}=\left | f(x) \cap f(y) \right |$,$\max \left \{ x,y\right \}=\left | f(x) \cup f(y) \right |$。于是得到如下式子: $$ \max_{i=1}^{n} \left \{ a_i \right \}=\left | \bigcup_{i=1}^{n} f(a_i) \right | $$ $$ =\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \left | \bigcap_{j \in T}f(a_j) \right | $$ $$ =\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \min_{j \in T} \left \{ a_{j} \right \} $$ 证毕,min 的计算过程的证明与 max 的一样。 # min-max 容斥求解数学期望 ## 前置知识:数学期望具有线性性质 对于两个变量 $x$ 和 $y$,以及两个常数 $a$ 和 $b$,有如下线性性质: $$ E(ax+by)=aE(x)+bE(y) $$ 因此,min-max 容斥可带入到期望的计算当中: $$ E(\max_{i=1}^{n} \left \{ a_i \right \})=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} E(\min_{j \in T} \left \{ a_{j} \right \}) $$ ## 前置知识:离散随机变量的几何分布 假设一个变量 $x$ 表示实验第一次成功的实验次数,实验成功的概率为 $p$,显然: $$ P(x=k)=p(1-p)^{k-1},k \in \mathbb{N}^{+} $$ 则变量 $x$ 的数学期望为: $$ E(x)=\sum_{i=1}^{\infty}i\cdot p(1-p)^{i-1}=p\sum_{i=1}^{\infty}i(1-p)^{i-1} $$ 考虑如何化简此式,我们知道几何级数: $$ \sum_{n=0}^{\infty}x^n=\frac{1}{1-x} $$ 这个可以由等比数列求和直接求得,该式只在 $x \in [0,1)$ 成立,因为该式只在 $x \in [0,1)$ 时收敛,对等式两边同时求导,得到如下式子: $$ \sum_{n=1}^{\infty} nx^{n-1}=\frac{1}{(1-x)^2} $$ 代入 $E(x)$ 得: $$ E(x)=p\cdot \frac{1}{p^2}=\frac{1}{p} $$ ## 问题一 **描述:** 有 $n$ 张卡牌,每张卡牌的数字都不一样,背面都一样,将所有卡牌背面朝上放在桌子上,从中随机抽取一张记下其数字,然后放回,需要抽 $k$ 次卡牌才可以看到所有的数字,求 $E(k)$,时间复杂度要求 $O(n)$。 **思路:** 设 $T_i$ 表示第一次看到第 $i$ 张卡牌的次数,则有如下: $$ E(k)=E(\max_{i=1}^{n} \left \{ T_i \right \}) $$ $$ =\sum_{S \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | S \right | -1} E(\min_{j \in S} \left \{ T_{j} \right \}) $$ 考虑如何求 $E(\min_{j \in S} \left \{ T_{j} \right \})$,$\min_{j \in S} \left \{ T_{j} \right \}$ 表示第一次抽取到集合 $S$ 的卡牌的抽取次数,考虑几何分布,其期望值即为抽到集合 $S$ 中任意一张卡牌的概率的倒数,如下: $$ E(\min_{j \in S} \left \{ T_{j} \right \})=\frac{n}{\left | S \right |} $$ 带入原式,改变枚举方式,枚举子集大小,得到如下式子: $$ E(k)=n\sum_{i=1}^{n}\binom{n}{i}(-1)^{i-1}\frac{1}{i} $$ 化简到这里已经足够了,如果你有一定的高等数学基础,这个式子还可以继续化简,就得到了如下式子(不再说明计算过程): $$ E(k)=n\sum_{i=1}^{n}\frac{1}{i} $$ ## 问题二([[HAOI2015] 按位或](https://www.luogu.com.cn/problem/P3175)) **描述:** 有一个变量 $x$ ,最初 $x=0$,接下来每次操作从区间 $[0,2^n-1]$ 当中选择一个整数,然后 $x \gets x \operatorname{or} i$,$\operatorname{or}$ 表示按位或操作,选择整数 $i$ 的概率为 $p_i$,需要 $k$ 次才能使 $x=2^n-1$,求 $E(k)$,$n \le 20$。 **思路:** 当 $x=2^n-1$ 时,其二进制形式下的有 $n$ 位且都是 $1$,设 $T_i$ 表示 $x$ 在二进制形式下第 $i$ 位是 $1$ 的操作次数,$E(k)$ 表示为如下: $$ E(k)=E(\max_{i=0}^{n-1} \left \{ T_i \right \}) $$ $$ =\sum_{S \subseteq \left \{ 0,1,\cdots,n-1 \right \}}(-1)^{\left | S \right | -1} E(\min_{j \in S} \left \{ T_{j} \right \}) $$ 其中 $E(\min_{j \in S} \left \{ T_{j} \right \})$ 同样可以由几何分布得出,如下: $$ E(\min_{j \in S} \left \{ T_{j} \right \})=\frac{1}{\sum_{G \subseteq{S}} p_{f(G)}} $$ 其中 $f(G)=\sum2^{G_i}$,即 $G$ 所表示的原数,这里需要提前预处理出所有集合的子集和,可以考虑 SOS DP,也可以考虑 FMT,最后直接枚举就行了,时间复杂度为 $O(n2^n)$。
正在渲染内容...
点赞
0
收藏
0