Min-Max 容斥
Qinyao28
·
·
个人记录
Min-Max 容斥
2023.12.25~12.26
——补充于 黎凡老师 的讲义习题
OI Wiki
一、Min-Max 容斥（最值反演）
1.基本形式
设 \max(S) 表示集合 S 的最大值，\min(S) 表示集合 S 的最小值，则：
\displaystyle\max(S)=\sum_{T\subset S,T\not=\text{\O}}(-1)^{|T|-1}\min(T)
\displaystyle\min(S)=\sum_{T\subset S,T\not=\text{\O}}(-1)^{|T|-1}\max(T)
2.推广：Kth 大/小
设 \max_k(S) 表示集合 S 中的第 k 大值，则：
\displaystyle\max_k(S)=\sum_{T\subset S,|T|\ge k}(-1)^{|T|-k}\binom {|T|-1}{k-1}\min(T)
### 3.期望形式
$$\displaystyle E(\max(S))=\sum_{T\subset S}(-1)^{|T|+1}E(\min(T))$$
$E(\min(S)),E(\max_k(S)),E(\min_k(S))$ 同理。
## 二、题目
### 1.例题
[Card Collector](http://222.180.160.110:1024/problem/48789)
- $O(n2^n)$ DP
设 $dp[S]$ 表示抽取集合 $S$ 中所有卡片的期望次数。则 $dp[S]=\sum_{i\notin S}p[i](dp[S]+1)+\sum_{i\in S}p[i](dp[S\oplus i]+1)$，移项后 DP，注意什么卡片都没有的情况。
- $O(2^n)$ 容斥
>**期望 Trick**：设每次操作的成功概率为 $p$，则操作的期望次数 $E=\dfrac 1p$。
>
>理解一：
>
>$E=1+(1-p)E$，即先执行一次操作，代价为 $1$，若操作没有成功，之后又重复原来的状态。移项后得到 $E=\dfrac 1p$。
>
>理解二：
>
>枚举操作次数，$E=0+p+2(1-p)p+3(1-p)^2p+\cdots=p(1+2(1-p)+3(1-p)^2+\cdots)=p\dfrac{1-(1-p)^\infty}{p(1-(1-p))}=\dfrac 1p$。（[“等差乘等比”型的三种求和方式](https://zhuanlan.zhihu.com/p/50156796)）
设 $dp[S]$ 表示至少抽取一张 $S$ 中卡片的期望次数（$E(\min (S))$）。则一次操作成功的概率为 $\sum_{i\in S}p[i]$，所以 $dp[S]=\dfrac 1{\sum_{i\in S}p[i]}$ 。
需要求抽取所有卡片的期望次数（$E(\max(S))$），套用容斥公式即可。
### 2.习题
- [按位或](https://www.luogu.com.cn/problem/P3175)；
- [随机游走](https://www.luogu.com.cn/problem/P5643)；[Become Big For Me](https://www.luogu.com.cn/problem/CF1687E)；[重返现世](https://www.luogu.com.cn/problem/P4707)；