广告 : 炫酷反演魔术

这个东西看起来挺冷门的，不过要是考的话到不会还真做不出来……

这东西也不是很复杂，本文应该不会太长吧……

我们现在有一个全集 $U=\{a_1,a_2,a_3,...,a_n\}$

我们设 $\large{\min(S)=\min\limits_{a_i∈S}a_i}$(集合里的最小值)

相应的 $\large{\max(S)=\max\limits_{a_i∈S}a_i}$(集合里的最大值)

假设我们能很轻松地求出任意集合的 $\min(S)$ ，但是我们不会(或者很难)求出任意集合的 $\max(S)$ 。

Min-Max容斥就是通过一种奥妙重重的方式把,Min转换成Max(或者反之)。

结论：

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

为什么是正确的呢？

我们设 $U$ 以内的元素互不相同，如果相同的话我们就以编号为序，不影响后续推导。

我们设 $A_k$ 为 $U$ 内元素降序排序后排名第 $k$ 的元素,也就是第 $k$ 大。

设 $\min(S)=A_k$ 那么 $S$ 有那些情况呢？

1）$k=1$

我们想得到的就是$A_1$。

令 $\min(S)=A_1$，很明显只有一种可能那就是$S=\{A_1\}$

所以贡献是$(-1)^{2}A_1=A_1$

2）$k>1$

最小的元素是 $A_k$ ，那么集合内不能存在比 $A_k$ 小的 $A_{k+1...n}$ ,而只能存在 $A_{1...k}$ 。

$A_k$必然在$S$内，剩下有$2^{k-1}$种选法。

通过人类智慧得知，这$2^{k-1}$种选法之中，有$2^{k-2}$种$|S|$是偶数，有$2^{k-2}$种$|S|$是奇数。

那么偶数的情况乘以$-1$，奇数的情况乘以$1$，刚好消掉了。

贡献为 $0$

综上，除了$\min(S)=\max(S)$的那一个$S$,其余的贡献都消掉了。最后，贡献和是$\max(S)$。

当然也可以把 $\max$ 转换成 $\min$ ,公式是 $\min(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\max(T)$ ,十分对称。

附：Min-Max容斥定理在期望下也成立。

也就是说 $E(\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\min(T))$

这是非常有用的，因为期望下的 $\max$ 和 $\min$ 是很难求的。

假设有 $a,b$ 两个不相关变量，则 $E(\max(a,b))≠\max(E(a),E(b))$。

例子：抛硬币， $a=b=\begin{cases}0(50\%) \\ 1(50\%)\end{cases}$ ,则 $E(a)=E(b)=\dfrac{1}{2}$

那么 $\max(a,b)=\begin{cases}\max(0,0)(25\%)\\ \max(0,1)(25\%)\\ \max(1,0)(25\%)\\ \max(1,1)(25\%)\end{cases}$ ,则 $E(\max(a,b))=0.75$

但是$\max(E(a),E(b))=0.5$所以期望不能大力拆 $\max$ 或 $\min$ 。

• 例题 : P3175 [HAOI2015]按位或

第一眼看去很难把这道题和Min-Max容斥联想起来（目前而言）

由于或运算时每个位都是独立的，我们可以把每个位分开来看。

我们设$a_k$为第$k$个二进制位变为$1$的时间。

那么我们要求的就是$E(\max(U))$（$U$为全集）。

如何求出$E(\min(S))$呢？

离散期望计算公式$E(x)=\sum v*P(v)$，意思就是($\sum$值*对应概率)。

我们设$P(S)$为选中集合$S$的概率，$P'(S)$为选中$S$的子集的概率。($U$为全集)

那么$\min(S)=k$的概率就是：前k-1次选了$S$的补集的子集，最后一次不能选$S$的补集的子集。

得到$\min(S)'s\ P(k)=P'(S⊕U)^{k-1}(1-P'(S⊕U))$

那么，$E(\min(S))=\sum\limits_{k=1}^∞k*P(k)=\sum\limits_{k=1}^∞k*P'(S⊕U)^{k-1}(1-P'(S⊕U))$

设$P'(S⊕U)=p$

$=(1-p)\sum\limits_{k=1}^∞k*p^{k-1}$

后面的式子就是等差*等比求和，错位相减：

$A=[1*1,2*p,3*p^2...k*p^{k-1}...],$求$Sum$

$Sum=1*p^0+2*p^1+3*p^2+...$

整体乘$p$得到：$p*Sum=1*p+2*p+3*p+...$

两式相减得到: $(1-p)Sum=1*p^0+(2-1)p+(3-2)p^2+...=\dfrac{1-p^{∞}}{1-p}$

因为 $0\leq p<1$ ,所以 $p^∞=0$ ,得到 $(1-p)Sum=\dfrac{1}{1-p}$

所以 $E(\min(S))=\dfrac{1}{1-P'(S⊕U)}$

我们的目标是要求出 $E(\min(\text{所有集合}))$ ,为了完成这个，我们要求出 $P'(\text{所有集合})$ 。

我们知道 $P'(S)=\sum\limits_{T\subseteq S}P(T)$ ,肉眼可见枚举子集。

$O(3^n)$ 肯定是会TLE的，所以请使用位运算卷积

$Or$ 卷积的 $DWT$ 相当于子集求和,那么直接上就好了。

#include<algorithm>
#include<cstdio>
#define Maxn 1100000
using namespace std;
int n;
double a[Maxn];
int siz[Maxn];
int main()
{
  scanf("%d",&n);n=(1<<n);
  for (int i=0;i<n;i++)scanf("%lf",&a[i]);
  for (int len=1;len<n;len<<=1)
    for (int p=0;p<n;p+=len+len)
      for (int i=p;i<p+len;i++)
        a[i+len]+=a[i];
  double ans=0;
  for (int i=1;i<n;i++){
    siz[i]=siz[i>>1]+(i&1);
    double sav=(1-a[i^(n-1)]);
    if (sav<1e-8){puts("INF");return 0;}
    sav=1/sav;
    ans+=(siz[i]&1) ? -sav:sav;
  }printf("%.10lf",-ans);
  return 0;
}

• 扩展形式

如果要求第$k$大呢?那怎么办?

我们仍然考虑使用容斥(消去)的方法:

$Kth\!\max(S)=\sum\limits_{T\subseteq S}F(|T|)\min(T)$

$F$是一个函数,根据直觉是可以构造出来的……

仿照上面的证明方法来构造:

设一个元素$x$排名为第$p$大,

那么有只有不包含比它小的$n-p+1$个元素时,$\min(T)=x$,有$p-1$个元素可供随意选择,而且必然选择$x$。

贡献系数是$\sum\limits_{i=1}^{p-1}\dbinom{p-1}{i}F(i+1)$。

我们要令这个$=[p=k]$,也就是$\sum\limits_{i=1}^{p}\dbinom{p}{i}F(i+1)=[p=k-1]$

接下来使用二项式反演,还不会的同学请见“炫酷反演魔术”。

二项式反演得到 $F(p+1)=\sum\limits_{i=1}^p(-1)^{p-i}\dbinom{p}{i}[i=k-1]=(-1)^{p-k+1}\dbinom{p}{k-1}$

所以 $F(p)=\sum\limits_{i=1}^p(-1)^{p-i}\dbinom{p}{i}[i=k-1]=(-1)^{p-k}\dbinom{p-1}{k-1}$

那么一开始的式子就变成了:

$Kth\!\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min(T)$

我们带入$k=1$的情况,发现$1th\!\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\dbinom{|T|-1}{0}min(T)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)$

正和上面的经典形式相同。

喜闻乐见的是,扩展Min-Max容斥也是在期望意义下成立的,即:

$E(Kth\!\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))$

• 例题 : P4707 重返现世

题意:每秒按固定概率出现物品,求收集到 $k$ 个物品的期望时间。

这道题还是很有难度的,这个黑牌不亏(或者是我的dp太菜了……)

分析:我们设集合 $S$ 为某些物品的集合,物品的权值为第一次出现时间。

那么 $E(\min(S))$ 就是这些物品中有其中一个出现的期望时间。

每一次得到 $S$ 中物品的概率是 $\sum\limits_{i∈S}p_i$,那么期望时间就是$\dfrac{1}{\sum\limits_{i∈S}p_i}$。

我们能求 $E(\min(S))$ 了,我们再想想, $E(Kth\!\min(U))$ ( $U$ 是全集)不就相当于期望耗时吗?

我们令下文的 $k=n-k+1$ ,求的就是 $E(Kth\!\max(U))$ 了,同时在题目中看到,这里的 $k<=11$ 。

套用上面的扩展Min-Max容斥,我们就得到了式子:

${\rm Ans}=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))$

但是这里的 $n\leq 1000$ 不能直接$O(2^n)$统计……

更新于 2026/7/5 06:20:07 作者

command_block

我们观察发现, $m<=10000$ ,一道数数题居然限制值域? 没准是复杂度和 $m$ 有关的 $dp$。

这个 $dp$ 十分复杂,具体过程就不放在这里了,其余请见 题解 P4707 【重返现世】

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

总结:

Min-Max容斥,考察范围较窄,学过的基本一眼就能看出来(flag)

但是可以结合期望,集合求和dp优化或者容斥,二项式反演来考,所以难度还是挺大的。

况且近年来都喜欢出毒瘤数数题,这玩意以后可能会被出成没有这么模板的题目吧,期待ing~