Min-Max 容斥

概述

Min-Max 容斥可以将序列最大值、最小值联系起来。它有两个公式。

我们令 $\min(S)$ 表示集合 $S$ 的最小值，$\max(S)$ 表示集合 $S$ 的最大值，$|S|$ 表示集合 $S$ 中元素的数量，则：

$$\max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)$$ $$\min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T)$$

证明

我们这里证明第一个公式。第二个公式的证明方法与它类似。

对于某一个数字 $x$，我们求当 $x$ 作为子集最大值时，系数之和是多少。

假设有 $k$ 个数字 $<x$。如果某个子集的最大值是 $x$，则这 $k$ 个数字可选可不选， $x$ 必须选，其他数字必须不选。我们枚举这 $k$ 个数字中被选的数量 $l$，此时 $|T|=l+1$，所以 $x$ 的系数之和就是

$$\sum_{l=0}^k\binom{k}{l}(-1)^k$$

由二项式定理得

$$\sum_{l=0}^k\binom{k}{l}(-1)^k=\sum_{l=0}^k\binom{k}{l}1^{k-i}(-1)^k=(1-1)^k=0^k$$

所以，当 $k\neq 0$（即 $x$ 不是最大值时），系数为 $0$。当 $k=0$（即 $x$ 是最大值时），系数为 $1$。所以最终的结果就是 $S$ 的最大值。

在期望中的应用

假设 $S$ 是一个随机序列，则序列期望最大值、期望最小值的关系，也可以用 Min-Max 容斥来表示。

$$E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T))$$ $$E(\min(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\max(T))$$

Luogu P3175 按位或

题目链接

假设我们有长度为 $n$ 的序列 $S_0\sim S_{n-1}$，其中 $S_i$ 表示：数字的第 $i$ 位经过了 $S_i$ 次操作后才变成了 $1$。那么题目求的是 $S$ 的期望最大值，即 $E(\max(S))$。

我们考虑 Min-Max 容斥。对于每个子集 $T$，我们求出它的期望最小值 $E(\min(T))$，即期望下经过多少次操作，这个子集中才有数字变成了 $1$。

假设 $P(T)$ 表示随机选一个数字，这个数字与 $T$ 有交集的概率。即 $P(T)=\sum_{i\cap T \neq \varnothing} p_i$。那么 $E(\min(T))=\frac{1}{P(T)}$。

我们考虑如何求 $P(T)$。正难则反，我们用 $1$ 减去不符合条件的和：

$$P(T)=1-\sum_{i\cap T = \varnothing} p_i=1-\sum_{i \subseteq(U-T)} p_i$$

减号后面的东西可以用 FWT 求。

至此，对于每个子集 $T$，我们都求出了 $E(\min(T))$。我们套用 Min-Max 容斥的公式，就可以求出 $E(\max(S))$。

AGC038E Gachapon

题目链接

我们假设有长度为 $n$ 的序列 $S$，表示第 $i$ 个数字经过 $S_i$ 次操作后成为合法元素。那么答案就是 $E(\max(S))$。

我们考虑一个子集 $T$ 的 $E(\min(T))$。它的含义是：子集内存在合法元素的期望次数。我们设所有 $a_i$ 的和为 $S_a$，子集 $T$ 内 $a_i$ 的和为 $S_T$。

我们假设每一次取数字，都可以取到 $T$ 集合内的数字。我们设在这种条件下，子集内存在合法元素的期望次数为 $E$。

我们用 $P(t=x)$ 表示子集 $T$ 中有合法元素时，操作次数恰好等于 $x$ 的概率；用 $P(t\ge x)$ 表示子集 $T$ 中有合法元素时，操作次数 $\ge x$ 的概率。那么

$$E=\sum_{k=1}^\infty k\times P(t=i)=\sum_{k=1}^\infty\sum_{j=k}^\infty P(t=j)=\sum_{k=1}^\infty P(t\ge k)$$

我们思考 $P(t\ge x)$ 的含义。它表示进行 $x-1$ 次操作后，$T$ 中没有合法元素的概率。那么上述式子的值就是，进行 $0$ 次操作后没有合法元素的概率，加上进行 $1$ 次后的概率，进行上第 $2$ 次后的概率，一直加下去。

我们求进行 $k$ 次操作后没有合法元素的概率。枚举每个数字被抽到的次数 $c_i$，满足 $\sum_{i\in T}c_i=k,c_i<b_i$。概率可以用（按顺序依次选取的概率 $\times$ 重排后可以得到的不同方案数）求出：

$$(\prod_{i\in T} (\frac{a_i}{S_T})^{c_i})\times(\frac{k!}{\prod_{i \in T}c_i!})=k!\prod_{i\in T}\frac{a_i^{c_i}}{S_T^{c_i}c_i!}=\frac{k!}{S_T^k}\prod_{i\in T}\frac{a_i^{c_i}}{c_i!}$$

此时 $P(t\ge k)$ 就是 $c_i$ 所有不同的取法的概率总和。所以

$$\begin{aligned} E&=\sum_{k=1}^\infty P(t\ge k)\\ &=\sum_k\sum_{c_i<b_i,\sum_{i\in T}c_i=k} \frac{k!}{S_T^k}\prod_{i\in T}\frac{a_i^{c_i}}{c_i!}\\ &=\sum_k\frac{k!}{S_T^k}\sum_{c_i<b_i,\sum_{i\in T}c_i=k}~~ \prod_{i\in T}\frac{a_i^{c_i}}{c_i!} \end{aligned}$$

不要忘记 $E$ 是只能选 $T$ 中的数字时的期望。如果所有数字都可以选，那么期望下每取 $\frac{S_a}{S_T}$ 个数字，可以取到一个 $T$ 中的数字。所以：

$$\begin{aligned} E(\min(T)) &=\frac{S_a}{S_T}\times E\\ &=\frac{S_a}{S_T} \sum_k\frac{k!}{S_T^k}\sum_{c_i<b_i,\sum_{i\in T}c_i=k}~~ \prod_{i\in T}\frac{a_i^{c_i}}{c_i!}\\ &=S_a \sum_k \frac{k!}{S_T^{k+1}}\sum_{c_i<b_i,\sum_{i\in T}c_i=k} ~~\prod_{i\in T}\frac{a_i^{c_i}}{c_i!}\\ \end{aligned}$$

我们根据 Min-Max 容斥的公式可得：

$$\begin{aligned} E(\max(S))&=\sum_{T\subseteq \{1,2,\dots,n\}}(-1)^{|T|+1}E(\min(T)) \\ &=\sum_{T\subseteq \{1,2,\dots,n\}}(-1)^{|T|+1}S_a \sum_k \frac{k!}{S_T^{k+1}}\sum_{c_i<b_i,\sum_{i\in T}c_i=k} ~~\prod_{i\in T}\frac{a_i^{c_i}}{c_i!}\\ &=\sum_{T\subseteq \{1,2,\dots,n\}}-S_a \sum_k \frac{k!}{S_T^{k+1}}\sum_{c_i<b_i,\sum_{i\in T}c_i=k} ~~\prod_{i\in T}-\frac{a_i^{c_i}}{c_i!}\\ \end{aligned}$$

我们考虑式子右边的 $\sum_{c_i<b_i,\sum_{i\in T}c_i=k} \prod_{i\in T}(-1)\frac{a_i^{c_i}}{c_i!}$ 怎么求。设 $f_{i,j,k}$ 表示只从前 $i$ 项里选，$S_T=j$，$\sum_{i\in T}c_i=k$ 的这个式子的值。转移分两种情况。

• $i$ 不选

$$f_{i,j,k}\leftarrow f_{i-1,j,k}$$

• $i$ 选
  枚举被抽中的次数 $c_i \in [0,b_i]$。

$$f_{i,j,k}\leftarrow -f_{i-1,j-a_i,k-c_i}\times \frac{a_i^{c_i}}{c_i!}$$

对所有 $j, k$ 计算 $-S_a \frac{k!}{j^{k+1}} f_{n,j,k}$ 并求和，就是最终答案。