给出集合\(S?\)，可以通过某种奇特的方式将最小值和最大值互相转化，甚至转化为\(k?\)大值。
更为有用的是，它在期望意义下也是正确的。
\[ min(S)=\sum_{\varnothing\neq T \subseteq S} (-1)^{|T|+1} max(T)\max(S)=\sum_{\varnothing\neq T \subseteq S} (-1)^{|T|+1} min(T) \]
证明和作用不再赘述，网上大把。
\(min-max\)容斥不只可以搞出最值，甚至可以搞出\(k\)大值。
受上面的启发，我们仍然考虑一个容斥：
\[ kthmax(S)=\sum_{\varnothing\neq T\subseteq S}f(|T|) min(T) \]
其中\(f(x)\)是一个未知的函数，我们需要将其构造出来。
对于一个排名为\(x\)的元素（即第\(n-x+1\)大），它对答案的贡献系数是这样一个东西：
\[ \sum_{i=0}^{n-x} {n-x \choose i} f(i+1) \]
我们令
\[ \sum_{i=0}^{n-x} {n-x \choose i} f(i+1)=[n-x+1=k]=[n-x=k-1] \]
得到
\[ \begin{align*} [a=k-1]&=\sum_{i=0}^a {a \choose i} f(i+1)\\end{align*} \]
由二项式反演，得
\[ \begin{align*} f(m+1)&=\sum_{i=0}^m {m \choose i} (-1)^{m-i}[i=k-1]\&={m \choose k-1} (-1)^{m-k+1}\\end{align*}\\therefore f(m)={m-1\choose k-1} (-1)^{m-k} \]
于是我们有
\[ kthmax(S)=\sum_{\varnothing\neq T\subseteq S}{|T|-1\choose k-1} (-1)^{|T|-k} min(T) \]
更好的是，这个式子在期望意义下仍然成立，即
\[ E(kthmax(S))=\sum_{\varnothing\neq T\subseteq S}{|T|-1\choose k-1} (-1)^{|T|-k} E(min(T)) \]
（然而我并不会证明……）
考虑这样一道题：
有一些物品\(a_i\)。在每个时刻，\(a_i\)出现的概率为\(p_i\)，其中\(\sum_i p_i=1\)。每个时刻会且仅会出现一个物品，问期望多久时间能收集到\(k\)个不同的物品。\(n\leq 20\)
对于一个集合\(S=\{a_{t_i}|1\leq i \leq m\}\)，定义\(min(S)\)为\(S\)中最早出现的物品出现的时间，\(max,kthmax\)同理，就可以套用上面的式子：
\[ E(kthmax(S))=\sum_{\varnothing\neq T\subseteq S}{|T|-1\choose k-1} (-1)^{|T|-k} E(min(T)) \]
其中$E(min(T))=\frac{1}{\sum p_{t_i}} $。
于是我们预处理阶乘、\(E(min(T))\)，然后大力枚举\(T\)，就可以在\(O(2^n)\)的时间内得到答案了。（可能有更快的做法？懒得想了）
洛谷P3175 [HAOI2015]按位或
洛谷P4707 重返现世
原文：https://www.cnblogs.com/p-b-p-b/p/10350374.html