Min-Max 容斥是通过容斥集合的最小值来得到集合最大值的一种方法。结合期望的线性性，我们得以计算几个随机变量最值的期望，它往往不和这些变量期望的最值相等。
Min-Max 容斥
Min-Max 容斥表明，对于集合 \(S\)，
\[\max(S) = \sum \limits_{T \subseteq S} (-1)^{|T|+1} \min(T) \]因为 \(S\) 是一个集合，因此其中的元素互不相同（如果实际应用时有重复元素，就按照编号排序）。设 \(A_k\) 表示 \(S\) 中第 \(k\) 大的元素，然后依次考虑对于每个 \(A_k\)，它对等式右边的贡献。
-
\(k=1\)
当且仅当 \(T = \{A_1\}\) 时 \(\min(T) = A_1\)，因此 \(A_1\) 的贡献为 \((-1)^2A_1 = A_1\)。
-
\(k>1\)
此时集合只能由 \(A_1 \sim A_{k-1}\) 中的任意多个加上 \(A_k\) 构成，这样的集合一共有 \(2^{k-1}\) 个，显然有 \(2^{k-2}\) 个集合大小为奇数，\(2^{k-1}\) 个集合大小为奇数，\(A_k\) 的贡献为 \((2^{k-2}-2^{k-2})A_k = 0\)。
因此最后等式右边只剩下 \(A_1\)，它就是 \(\max(S)\)。
同样地，我们有
\[\min(S) = \sum \limits_{T \subseteq S} (-1)^{|T|+1} \max(T) \]注意到 \(\min\) 和 \(\max\) 本来就对称，对上面的证明稍作修改即可。
扩展 Min-Max 容斥
Min-Max 容斥可以扩展到 \(k\) 大。我们还是希望对 \(\min(T)\) 容斥得到 \(\operatorname{kthmax}(S)\)，但容斥系数 \(f(|T|)\) 可能和上面不同，即
\[\operatorname{kthmax}(S) = \sum \limits_{T \subseteq S} f(|T|) \min(T) \]考虑 \(A_p\) 对等式右边的贡献系数。根据上面的讨论，如果 \(\min(T)=A_p\)，集合只能由 \(A_1\sim A_p\) 中的若干个组成，且必须包含 \(A_p\)。我们希望仅当 \(p=k\) 时，\(A_p\) 贡献 \(1\) 的系数，其它时候都是 \(0\)，于是有
\[\sum \limits_{i=0}^{p-1} \dbinom{p-1}{i} f(i+1) = [p=k] \]用 \(p+1\) 替换 \(p\)，有
\[\sum \limits_{i=0}^{p} \dbinom{p}{i} f(i+1) = [p=k-1] \]令 \(G(i) = f(i+1),F(i) = [i=k-1]\)，则
\[F(n) = \sum \limits_{i=0}^n \dbinom{n}{i} G(i) \]二项式反演得
\[G(n) = \sum \limits_{i=0}^n (-1)^{n-i} \dbinom{n}{i} F(i) \]展开得
\[f(n+1) = \sum \limits_{i=0}^n (-1)^{n-i} \dbinom{n}{i} [i=k-1] = (-1)^{n-k+1} \dbinom{n}{k-1} \]\[f(n) = (-1)^{n-k} \dbinom{n-1}{k-1} \]因此
\[\operatorname{kthmax}(S) = \sum \limits_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} \min(T) \]Min-Max 容斥和期望
根据期望的线性性，有 \(E[X+Y] = E[X]+E[Y]\)。因为在 Min-Max 容斥的过程中，我们只使用了线性运算，于是它对期望成立，这几乎是显然的。也就是说，
\[E(\max(S)) = \sum \limits_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \]\[E(\operatorname{kthmax}(S))= \sum \limits_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} E(\min(T)) \]例 1 [HAOI2015]按位或
题意
有一个数字 \(v\)，初值为 \(0\)。每秒会随机选择一个 \([0,2^n-1]\) 的数字 \(x\)，令 \(v\) 变为 \(v \operatorname {or} x\)，其中 \(\operatorname{or}\) 是按位或。选中 \(x\) 的概率是 \(p_x\)。
问 \(v\) 期望多少秒变成 \(2^n-1\)，或判断无解。
\(0 \leq n \leq 20,0 \leq p_x \leq 1,\sum p_x = 1\)
题解
注意到位之间独立，可以看作一个 \(n\) 元素集合，每秒的操作看作选出一个它的子集，于是我们设全集 \(U\) 为全部 \(n\) 个元素都被选择过的时间，要计算的就是 \(E(\max(U))\)。
根据 Min-Max 容斥，
\[E(\max(S)) = \sum \limits_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \]只需要计算 \(E(\min(T))\) 即可，即集合 \(T\) 中有至少一个元素被选择过的期望时间。如果我们知道了每次选出的集合 \(G\) 和 \(T\) 有交的概率 \(p_0\)，那么期望时间就是 \(\dfrac{1}{p_0}\)。
为此，我们希望计算所有满足 \(G \cap T \neq \varnothing\) 的集合 \(G\) 的 \(p_G\) 之和。注意到这有点难算，不妨取 \(T\) 的补集 \(T^c\)，其子集一定和 \(T\) 没有交。现在的问题就是计算 \(f_{S_0} = \sum \limits_{T_0 \cup S_0 = S_0} p_{S_0}\)。FWT 即可。
最后的答案即
\[\sum \limits_{T \subseteq U} (-1)^{|T|+1} \dfrac{1}{1-p_{U\backslash T}} \]为什么是 \(1-p_{U\backslash T}\) 呢，因为 \(p_{U\backslash T}\) 是选不到和 \(T\) 有交的集合的概率，注意 \(E(\min(\varnothing))\)就别用 \(\dfrac{1}{1-1}\) 来算了，直接跳过这一项就好，反正它等于 \(0\)。
时间复杂度 \(O(2^n)\)。
# include <bits/stdc++.h>
const int N=1048580;
int n;
double p[N];
int bc[N];
int main(void){
scanf("%d",&n);
for(int i=0;i<(1<<n);++i)
scanf("%lf",&p[i]);
for(int i=1;i<(1<<n);++i)
bc[i]=bc[i>>1]+(i&1);
for(int l=2,s=1;l<=(1<<n);l<<=1,s<<=1){
for(int i=0;i<(1<<n);i+=l){
for(int j=0;j<s;++j)
p[i+j+s]+=p[i+j];
}
}
int U=(1<<n)-1;
double ans=0;
for(int i=1;i<=U;++i){
if(1-p[U^i]<1e-10){
printf("INF");
return 0;
}
ans+=1.0/(1-p[U^i])*((bc[i]&1)?1:-1);
}
printf("%.8lf",ans);
return 0;
}
例 2 Luogu P4707 重返现世
题意
有 \(n\) 种原料，每一秒会随机出现一种原料，第 \(i\) 种原料出现的概率是 \(\dfrac{p_i}{m}\)。如果之前没有这种原料，主人公就会对它进行收集。求主人公收集到 \(k\) 种原料的期望时间。
\(1 \leq n \leq 1000,1 \leq k \leq n,0 \leq n-k \leq \textbf{10},0 \leq p_i \leq m,\sum p_i =m,1 \leq m \leq 10^4\)
题解
一眼暴力扩展 Min-Max 容斥。
\[E(\operatorname{kthmin}(S))= \sum \limits_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} E(\max(T)) \]我们发现 \(\max(T)\) 不怎么好算。不妨将 \(k\) 变为 \(n-k+1\)，这样 \(k\) 小变成了 \(k\) 大，并且还有一个好性质：现在 \(1 \leq k \leq 11\) 了！
\[E(\operatorname{kthmax}(S))= \sum \limits_{T \subseteq S} (-1)^{|T|-k} \dbinom{|T|-1}{k-1} E(\min(T)) \]后面的 \(E(\min(T))\) 等于 \(\dfrac{m}{\sum \limits_{i \in T} p_i}\)。如果暴力算会寄掉，但因为 \(m \leq 10^4\)，我们可以考虑一些依赖 \(m\) 的算法。考虑到，如果 \(|T|\) 相同，\(\sum \limits_{i \in T} p_i\) 相同，那么它们对答案的贡献就应该相同。
尝试把这些状态分到一类，设 \(dp(i,j,s)\) 表示前 \(i\) 个数选了 \(j\) 个，\(p_i\) 之和等于 \(s\) 的方案数。考虑刷表， \(dp(i-1,j,s)\) 可以刷到 \(dp(i,j,s)\) 和 \(dp(i,j+1,s+p_i)\)。
复杂度 \(O(n^2m)\)，滚动数组可以 \(70\) 分。要优化只能从 \(j\) 这一维下手，砍掉这一维变成了 \(dp(i,s)\)，表示前 \(i\) 个数 \(p_i\) 之和等于 \(s\) 的方案中 \((-1)^{|T|-k} \dbinom{|T|-1}{k-1}\) 的和。
然后考虑下该怎么转移。不选还是一样的，从 \(dp(i-1,s)\)，刷到 \(dp(i,s)\)；如果要选 \(p_i\) 的话非常头疼，\(dp(i-1,s)\) 中的贡献到了 \(dp(i,s+p_i)\) 就变成了
\[(-1)^{|T|+1-k} \dbinom{|T|}{k-1} \]考虑怎样把这部分贡献用若干个 \(dp\) 值表示出来。拆掉组合数，变成
\[(-1)^{|T|+1-k} \dbinom{|T|-1}{k-2} + (-1)^{|T|+1-k} \dbinom{|T|-1}{k-1} \]\[=(-1)^{|T|-(k-1)} \dbinom{|T|-1}{k-2} - (-1)^{|T|-k} \dbinom{|T|-1}{k-1} \]右边那一坨就是 \(dp(i-1,s)\)，左边那一坨和右边很像啊...只有 \(k\) 有点差别，把 \(k\) 记进去就好了。
于是正确的方式：设 \(dp(i,k,s)\)，刷的时候 \(dp(i-1,k,s)\) 让 \(dp(i,k,s)\) 加上 \(dp(i-1,k,s)\)，让 \(dp(i,k,s+p_i)\) 加上 \(dp(i-1,k-1,s)-dp(i-1,k,s)\) 即可。
关于边界：\(dp(0,0,0)=0\)，\(dp(0,i,0)=1(i>0)\)。考虑 \(k=1\) 时需要将上式拓展到广义组合数意义下，容易知道 \(\dbinom{n}{-1}=0,\dbinom{n}{0}=1 (n \in \R)\)。
代码里面是填表法，跟背包差不多，好处是少了点边界情况。
# include <bits/stdc++.h>
const int N=10010,INF=0x3f3f3f3f,MOD=998244353;
int n,k,m;
int dp[N][12];
int p[N];
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int qpow(int d,int p){
int ans=1;
for(;p;p>>=1,d=1ll*d*d%MOD) (p&1)&&(ans=1ll*ans*d%MOD);
return ans;
}
int main(void){
n=read(),k=read(),m=read(),k=n-k+1;
for(int i=1;i<=n;++i) p[i]=read();
for(int i=1;i<=k;++i) dp[0][i]=-1;
for(int i=1;i<=n;++i){
for(int j=m;j>=p[i]&&p[i];--j)
for(int kp=k;kp;--kp) dp[j][kp]=((dp[j][kp]+dp[j-p[i]][kp-1]-dp[j-p[i]][kp])%MOD+MOD)%MOD;
}
int ans=0;
for(int i=1;i<=m;++i) ans=(ans+1ll*m*qpow(i,MOD-2)%MOD*dp[i][k]%MOD)%MOD;
printf("%d",ans);
return 0;
}