前言

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 重返现世题解