经常和概率期望题相结合。
对于全序集合 \(S\)，有：
\[\max S=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}\min T
\]
\]
\[\min S=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}\max T
\]
\]
证明
对于 \(x\in S\)，假设 \(x\) 是 \(S\) 中第 \(k\) 大的元素，则建立映射\(f:x\rightarrow \{1,2,\dots,k\}\)。
可以得到对于 \(x,y\in S\)，有：
\[f(\min (x,y))=f(x)\cap f(y)
\]
\]
\[f(\max (x,y))=f(x)\cup f(y)
\]
\]
因此得到：
\[\begin{aligned}
\vert f(\max S)\vert&=\bigg\vert \bigcup\limits_{x\in S}f(x)\bigg\vert \\
&=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\bigg\vert \bigcap\limits_{x\in T}f(x)\bigg\vert\\
&=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\ \vert f(\min T)\vert\\
\end{aligned}\]
\vert f(\max S)\vert&=\bigg\vert \bigcup\limits_{x\in S}f(x)\bigg\vert \\
&=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\bigg\vert \bigcap\limits_{x\in T}f(x)\bigg\vert\\
&=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -1}\ \vert f(\min T)\vert\\
\end{aligned}\]
将 \(\vert f(\max S)\vert\) 映射回原式，从而得证。
通俗的说，就是对于除本身集合的其他的集合取最小值时，集合大小为奇数时加上，大小为偶数时减掉，而选奇数个和选偶数个的方案数又是一样的，于是抵消掉了，最后只剩下 \(f(\max\limits_{x\in S} x)\)的贡献。
拓展
\[\max_k S=\sum\limits_{T\subseteq S,\vert T\vert\geq k}(-1)^{\vert T\vert -k}{\vert T\vert-1\choose k-1}\min T
\]
\]
背他就完了
应用
常见的应用：有 \(n\) 个变量，每个变量出现的概率为 \(p\)。问每一个变量都出现的期望时间。
根据期望的线性性质，可以得到
\[E(\max S)=\sum\limits_{T\subseteq S,T\not=\varnothing}(-1)^{\vert T\vert -1}E(\min T)
\]
\]
其中 \(E(\min T)\) 显然就是 \(\cfrac{1}{\sum\limits_{i\in T}p_i}\)。
例题：礼物
显然的 Min-max 容斥模板题。最大的喜悦值就是给出的喜悦值的和，而剩下就是套式子了。用 dfs 枚举子集 \(T\)，时间效率 \(O(2^n)\) ，空间效率 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn=30;
int n;
long long ans;
double res;
double p[maxn];
void dfs(int now,double sum,int opt){
if(now==n+1){
if(sum>1e-9)res+=1.0*opt/sum;
return;
}
dfs(now+1,sum+p[now],-opt);
dfs(now+1,sum,opt);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
long long u;
scanf("%lf%lld",&p[i],&u);
ans+=u;
}
printf("%lld\n",ans);
dfs(1,0,-1);
printf("%.3lf\n",res);
return 0;
}