min-max容斥小结

容斥

---

定义

对于一个集合$S$，
$\min(S)$表示其第一个出现的元素（$or$最小的元素），
$\max(S)$表示其最后一个出现的元素（$or$最大的元素）。

设$E(x)$表示元素$x$的期望出现次数（出现时是第几次）。
则有一个不可言妙的公式

$$E(\max(S))=\sum_{S'\in S}E(\min(S'))*(-1)^{|S'|+1}$$
至于证明。。。蒟蒻这辈子都不可能会的，挂个证明的链接

用途

• 对于一个集合$S$，给出每个元素出现的概率，我们需要求每一个元素都出现至少一次的期望次数（即$\max(S)$）时，可使用$min-max$容斥。

题目

• [HDU4336]Card Collector
  题解
• [PKUWC2018]随机游走
  题解