MinMax 容斥 学习笔记

基本形式

[ max(S) = sum_{Tsubseteq S, T neq varnothing} (-1)^{|T|-1}min(T) ]

证明

不提供数学证明。

简要讲一下抽象理解伪证：

考虑从大到小排名为 (i) 的数，这个数会作为集合 (T) 的最小值出现时，那么 (T) 剩下的所有值都是从大于它的数中选取的。那么选取方案就是 (binom{i-1}{|T|-1})。

如果 (i=1)，也就是 (a_i = max(S))，那么它只会被加上 (1) 次。

如果 (i>1)，那么它一共会被算 (sumlimits_{2notmid j, j=1}^{i-1} binom{i-1}{j-1} - sumlimits_{2mid j, j=2}^{i-1}binom{i-1}{j-1})。根据组合数的常识，这个东西在 (i-1>0) 的时候答案为 (0)。

综上所述，(max(S) = sumlimits_{Tsubseteq S, T neq varnothing} (-1)^{|T|-1}min(T)) 成立。证毕。

扩展1

[ min(S) = sum_{Tsubseteq S, T neq varnothing} (-1)^{|T|-1}max(T) ]

显然。

推广

令 (max_k(S)) 表示 (S) 中的第 (k) 大的值。

则
[ max _{k}(S) = sum_{Tsubseteq S, |T| geq k} (-1)^{|T|-k}binom {|T|-1}{k-1} min(T) ]

证明

类似于基本形式。

因为 (|T|geq k)，所以 (min(T) leq max_k(S))。

对于从大到小排列的第 (i) 个数，同基本形式，这个数会作为集合 (T) 的最小值出现时，那么 (T) 剩下的所有值都是从大于它的数中选取的。那么选取方案就是 (binom{i-1}{|T|-1})。

如果 (i=k)，那么它只会被计算 (1) 次，即 (T = {xmid xgeq a_i}) 时，同时 (binom{|T|-1}{k-1} = 1)。

如果 (i > k)，那么如上文所述，它会作为大小为 (|T|) 的集合出现的次数为 (binom{i-1}{|T|-1})。每一次出现会被计算 (binom{|T|-1}{k-1}) 次。所以它作为大小为 (|T|) 的集合出现的总贡献为 (binom{i-1}{|T|-1}binom{|T|-1}{k-1} = binom{i-1}{k-1}binom{i-k}{|T|-k})。所以 (i) 的总贡献为 (sumlimits_{2notmid j, j=k}^{i-1} binom{i-1}{k-1}binom{i-k}{j-k} - sumlimits_{2mid j, j=2}^{i-1}binom{i-1}{k-1}binom{i-k}{j-k} = binom{i-1}{k-1}(sumlimits_{2notmid j, j=k}^{i-1} binom{i-k}{j-k} - sumlimits_{2mid j, j=2}^{i-1}binom{i-k}{j-k}))。同样的，根据组合数的常识，(sumlimits_{2notmid j, j=k}^{i-1} binom{i-k}{j-k} - sumlimits_{2mid j, j=2}^{i-1}binom{i-k}{j-k}) 这个东西只有在 (i-k=0) 时才为 (1)，否则为 (0)。

应用1

常用的应用比如说：有 (n) 个变量，每个变量出现的概率为 (p)。问每一个变量都出现的期望时间。

不妨设每一个变量出现的时间为 (t_i)，那么全部出现的概率可以表示为 (t) 的最大值。至少出现一个就是 (t) 的最小值。

那么根据 MinMax​ 容斥的一般形式：
[ max(S) = sum_{Tsubseteq S, T neq varnothing} (-1)^{|T|-1}min(T) ]
同时，根据期望的线性性质，我们也有：
[ E(max(S)) = sum_{Tsubseteq S, T neq varnothing} (-1)^{|T|-1}E(min(T)) ]
而 (E(min(T))) 显然很好求解。（显然是 (frac 1p) 对吧

所以这个问题就解决了。

题目

HDU - 4336 Card Collector 题解

bzoj4036 [HAOI2015]按位或 题解

P4707 重返现世 题解

loj2542 「PKUWC2018」随机游走 题解