也叫最值反演 /cy
参考资料
引入
现在有一个全集${\rm U}$.
我们定义$\min (S)$为集合$S$中数值最小的元素,$\max (S)$为集合$S$中数值最大的元素.
假设我们已经求得任意集合的$\min(S)$,但是我们很难通过它求出任意集合的$\max (S)$.
而Min-Max容斥就是干这个事的,它可以通过一些神奇的变化,通过$\min(S)$,求出$\max(S)$,或者反之.
式子与推导
$$\max(S) = \sum_{W \subseteq S} (-1) ^ {|W| + 1} \min(W)$$
$$\min(S) = \sum_{W \subseteq S} (-1) ^ {|W| + 1} \max(W)$$
公式非常对称,所以说很好背啊.
我们以第一个式子为例(因为推导过程是类似的,所以不再重复).
首先我们设$T_k$为全集$\rm U$内元素的第$k$大元素.
设$\min(S) = T_k$,那么这时有两种情况:
$k = 1$
那么显然$S = \lbrace 1 \rbrace$,答案为$(-1)^2 T_1 = T_1$
$k > 1$
那么显然集合中只能包含$T_{1 \dots k}$.
$T_k \in S$是必然的,那么剩下的元素共有$2^{k - 1}$种选法($k - 1$个元素,每个元素可以选也可以不选).
那么在这些选法中,$\rm S$的大小一半为偶数,一半为奇数. 这样我们分别乘上$-1$和$1$,加起来就直接对消了,贡献为0.
所以,除了$\min(S) = \max(S)$的特定情况,其他集合的元素的贡献全部就对消了,我们也就得出答案了.
应用
所以上面的式子和推导有什么用啊.
喜闻乐见的是,Min-Max容斥的公式在期望意义下也是成立的,也就是说:
$$E(\max(S)) = \sum_{W \subseteq S} (-1) ^ {|W| + 1} E(\min(W))$$
$$E(\min(S)) = \sum_{W \subseteq S} (-1) ^ {|W| + 1} E(\max(W))$$
那么我们来看一道例题:HDU4336 Card Collector.
N个物品，每次得到第i个物品的概率为$p_i$，而且有可能什么也得不到，问期望多少次能收集到全部N个物品
我们设$T_i$表示第一次得到物品$i$的时间,那么题目要求的就是$E(\max(U)) \quad U = \lbrace T_1, T_2, \dots T_N \rbrace$
那么可以发现$\min(S)$其实等同于第一次获得物品的时间,显然:
$$P(\min(S)) = \sum_{i \in S} p_i$$
那么
$$E(\min(S)) = \frac {1}{P(\min(S))}$$
扩展
如果我们把Min-Max容斥扩展一下,要求第$k$大的期望,怎么做呢?
根据已有的Min-Max容斥公式和一些大胆的猜想,我们列出如下式子:
$${\rm Kth} \max(S) = \sum_{W \subseteq S} f(|W|) \min(W)$$
函数$f$是一个需要构造的东西,根据一些神奇的变换和二项式反演的有关知识(笔者不会证明),可以得到:
$${\rm Kth} \max(S) = \sum_{W \subseteq S} (-1)^{|W| + 1} C_{|W|-1}^{k-1} \min(W)$$
更加喜闻乐见的是，这个式子在期望意义下也是成立的:
$$E({\rm Kth} \max(S)) = \sum_{W \subseteq S} (-1)^{|W| + 1} C_{|W|-1}^{k-1} E(\min(W))$$
例题
也是To do list
先占个坑吧.