前言

PKUWC2018的D2T3好像是个Min-Max容斥板子题，还是要学习一下的。

用途

给定一个集合S，告诉你其中每个元素单位时间出现的概率，问你每个元素至少出现一次的期望时间。

Min-Max容斥

做这道题我们需要用到Min-Max容斥的结论，这里先来证明Min-Max容斥的正确性。
需要二项式反演的基础知识，不会二项式反演戳这里
给定集合S，令 $Max(S)$ 为S中的最大值， $Min(S)$ 为S中的最小值，有结论
$Max(S)=\sum\limits_{S’\subseteq S}Min(S’)*(-1)^{|S’|-1}$
这为什么是对的呢。
我们先考虑构造容斥系数 $f$ ，使得
$Max(S)=\sum\limits_{S’\subseteq S}Min(S’)*f_{|S’|}$
枚举第 $x+1$ 大值的贡献，也就是有多少个集合的最小值是全集的第 $x+1$ 大值。
那么比我大的x个可以随便选。
这个值为 $\sum\limits_{i=0}^{x}\binom{x}{i}*f_{i+1}$
考虑会对最后答案有贡献的只有 $x=0$ 的时候，所以
定义kronecker delta函数 $g(x)=[x=0]$
$g(x)=\sum\limits_{i=0}^{x}\binom{x}{i}*f_{i+1}$
直接二项式反演得到
$f_{x+1}=\sum\limits_{i=0}^{x}\binom{x}{i}*g_{i}*(-1)^{x-i}$
由于 $g$ 只在 $i=0$ 时为1，所以 $f_{x+1}=(-1)^{x}$
$f_{x}=(-1)^{x-1}$
$Max(S)=\sum\limits_{S’\subseteq S}Min(S’)*(-1)^{|S’|-1}$
同时这个结论在期望意义下也是成立的，那么这道题就可以做了。

做法

对于一个集合S，我们定义它的权值为它出现的时间。
$Min(S)$ 表示这个集合中最小的元素
$Max(S)$ 表示这个集合中最大的元素
$P[i]$ 表示i这个元素单位时间出现的概率， $E$ 表示期望时间
显然有 $Min(S)=\sum\limits_{i\in S}P(i)$ ，而 $E(Min(S))=\frac{1}{P(Min(S))}$
然后Min-Max容斥告诉我们 $E(Max(S))=\sum\limits_{S’\subseteq S}E(Min(S’))*(-1)^{|S’|-1}$
注意特判 $S’$ 不能是空集。

例题

例题一

贴个板子题先。
Hdu 4336 Card Collector
考虑每张牌如果都要出现，那么就是求 $Max(全集)$ ，直接套公式做就好了。

例题二

Luogu 3175 [HAOI 2015] 按位或
 Luogu 3175 [HAOI 2015] 按位或题解

例题三

LOJ 2542「PKUWC2018」随机游走
 LOJ 2542「PKUWC2018」随机游走题解

kth Min-Max容斥

顾名思义，就是可以求第k大元素出现的期望时间。
上面的公式求的是最大元素出现的期望时间，下面给出求第k大元素出现期望时间的公式。
$E(kthMax(S))=\sum\limits_{S’ \subseteq S}E(Min(S’))*(-1)^{|S’|-k}*\binom{|S’|-1}{k-1}$
把k=1带进去就得到了前面的那个公式。
证明思路与 $k=1$ 时如出一辙
先构造容斥系数 $f$ ，使得
$kthMax(S)=\sum\limits_{S’\subseteq S}Min(S’)*f_{|S’|}$
考虑第 $x+1$ 大值的贡献
这个值为 $\sum\limits_{i=0}^{x}\binom{x}{i}*f_{i+1}$
考虑会对最后答案有贡献的从 $x=0$ 变为了 $x=k-1$ 的，所以
定义kronecker delta函数 $g(x)=[x=k-1]$
$g(x)=\sum\limits_{i=0}^{x}\binom{x}{i}*f_{i+1}$
二项式反演
$f_{x+1}=\sum\limits_{i=0}^{x}\binom{x}{i}*g_{i}*(-1)^{x-i}$
由于 $g$ 只在 $i=k-1$ 时为1，所以 $f_{x+1}=(-1)^{x-k+1}*\binom{x}{k-1}$
$f_{x}=(-1)^{x-k}*\binom{x-1}{k-1}$
$kthMax(S)=\sum\limits_{S’ \subseteq S}Min(S’)*(-1)^{|S’|-k}*\binom{|S’|-1}{k-1}$
同样在期望意义下是对的。
也贴个题
Luogu 4707 重返现世
 Luogu 4707 重返现世题解