专栏文章

Min-Max容斥小记

ccommand_block
算法·理论参与者 56已保存评论 58

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
58 条
当前快照
1 份
快照标识符
@mhz5tvba
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
广告 : 炫酷反演魔术
这个东西看起来挺冷门的，不过要是考的话到不会还真做不出来……
这东西也不是很复杂，本文应该不会太长吧……
我们现在有一个全集 U={a1,a2,a3,...,an}U=\{a_1,a_2,a_3,...,a_n\}
我们设 min⁡(S)=min⁡ai∈Sai\large{\min(S)=\min\limits_{a_i∈S}a_i}(集合里的最小值)
相应的 max⁡(S)=max⁡ai∈Sai\large{\max(S)=\max\limits_{a_i∈S}a_i}(集合里的最大值)
假设我们能很轻松地求出任意集合的 min⁡(S)\min(S) ，但是我们不会(或者很难)求出任意集合的 max⁡(S)\max(S) 。
Min-Max容斥就是通过一种奥妙重重的方式把,Min转换成Max(或者反之)。
结论：
max⁡(S)=∑T⊆S(−1)∣T∣+1min⁡(T)\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)
为什么是正确的呢？
我们设 UU 以内的元素互不相同，如果相同的话我们就以编号为序，不影响后续推导。
我们设 AkA_k 为 UU 内元素降序排序后排名第 kk 的元素,也就是第 kk 大。
设 min⁡(S)=Ak\min(S)=A_k 那么 SS 有那些情况呢？
1）k=1k=1
我们想得到的就是A1A_1。
令 min⁡(S)=A1\min(S)=A_1，很明显只有一种可能那就是S={A1}S=\{A_1\}
所以贡献是(−1)2A1=A1(-1)^{2}A_1=A_1
2）k>1k>1
最小的元素是 AkA_k ，那么集合内不能存在比 AkA_k 小的 Ak+1...nA_{k+1...n} ,而只能存在 A1...kA_{1...k} 。
AkA_k必然在SS内，剩下有2k−12^{k-1}种选法。
通过人类智慧得知，这2k−12^{k-1}种选法之中，有2k−22^{k-2}种∣S∣|S|是偶数，有2k−22^{k-2}种∣S∣|S|是奇数。
那么偶数的情况乘以−1-1，奇数的情况乘以11，刚好消掉了。
贡献为 00
综上，除了min⁡(S)=max⁡(S)\min(S)=\max(S)的那一个SS,其余的贡献都消掉了。最后，贡献和是max⁡(S)\max(S)。
当然也可以把 max⁡\max 转换成 min⁡\min ,公式是 min⁡(S)=∑T⊆S(−1)∣T∣+1max⁡(T)\min(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\max(T) ,十分对称。
附：Min-Max容斥定理在期望下也成立。
也就是说 E(max⁡(S))=∑T⊆S(−1)∣T∣+1E(min⁡(T))E(\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}E(\min(T))
这是非常有用的，因为期望下的 max⁡\max 和 min⁡\min 是很难求的。
假设有 a,ba,b 两个不相关变量，则 E(max⁡(a,b))≠max⁡(E(a),E(b))E(\max(a,b))≠\max(E(a),E(b))。
例子：抛硬币， a=b={0(50%)1(50%)a=b=\begin{cases}0(50\%) \\ 1(50\%)\end{cases} ,则 E(a)=E(b)=12E(a)=E(b)=\dfrac{1}{2}
那么 max⁡(a,b)={max⁡(0,0)(25%)max⁡(0,1)(25%)max⁡(1,0)(25%)max⁡(1,1)(25%)\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.75E(\max(a,b))=0.75
但是max⁡(E(a),E(b))=0.5\max(E(a),E(b))=0.5所以期望不能大力拆 max⁡\max 或 min⁡\min 。
第一眼看去很难把这道题和Min-Max容斥联想起来（目前而言）
由于或运算时每个位都是独立的，我们可以把每个位分开来看。
我们设aka_k为第kk个二进制位变为11的时间。
那么我们要求的就是E(max⁡(U))E(\max(U))（UU为全集）。
如何求出E(min⁡(S))E(\min(S))呢？
离散期望计算公式E(x)=∑v∗P(v)E(x)=\sum v*P(v)，意思就是(∑\sum值*对应概率)。
我们设P(S)P(S)为选中集合SS的概率，P′(S)P'(S)为选中SS的子集的概率。(UU为全集)
那么min⁡(S)=k\min(S)=k的概率就是：前k-1次选了SS的补集的子集，最后一次不能选SS的补集的子集。
得到min⁡(S)′s P(k)=P′(S⊕U)k−1(1−P′(S⊕U))\min(S)'s\ P(k)=P'(S⊕U)^{k-1}(1-P'(S⊕U))
那么，E(min⁡(S))=∑k=1∞k∗P(k)=∑k=1∞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)=pP'(S⊕U)=p
=(1−p)∑k=1∞k∗pk−1=(1-p)\sum\limits_{k=1}^∞k*p^{k-1}
后面的式子就是等差*等比求和，错位相减：
A=[1∗1,2∗p,3∗p2...k∗pk−1...],A=[1*1,2*p,3*p^2...k*p^{k-1}...],求SumSum
Sum=1∗p0+2∗p1+3∗p2+...Sum=1*p^0+2*p^1+3*p^2+...
整体乘pp得到：p∗Sum=1∗p+2∗p+3∗p+...p*Sum=1*p+2*p+3*p+...
两式相减得到: (1−p)Sum=1∗p0+(2−1)p+(3−2)p2+...=1−p∞1−p(1-p)Sum=1*p^0+(2-1)p+(3-2)p^2+...=\dfrac{1-p^{∞}}{1-p}
因为 0≤p<10\leq p<1 ,所以 p∞=0p^∞=0 ,得到 (1−p)Sum=11−p(1-p)Sum=\dfrac{1}{1-p}
所以 E(min⁡(S))=11−P′(S⊕U)E(\min(S))=\dfrac{1}{1-P'(S⊕U)}
我们的目标是要求出 E(min⁡(所有集合))E(\min(\text{所有集合})) ,为了完成这个，我们要求出 P′(所有集合)P'(\text{所有集合}) 。
我们知道 P′(S)=∑T⊆SP(T)P'(S)=\sum\limits_{T\subseteq S}P(T) ,肉眼可见枚举子集。
O(3n)O(3^n) 肯定是会TLE的，所以请使用位运算卷积
OrOr 卷积的 DWTDWT 相当于子集求和,那么直接上就好了。
CPP
#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;
}
  • 扩展形式
如果要求第kk大呢?那怎么办?
我们仍然考虑使用容斥(消去)的方法:
Kth ⁣max⁡(S)=∑T⊆SF(∣T∣)min⁡(T)Kth\!\max(S)=\sum\limits_{T\subseteq S}F(|T|)\min(T)
FF是一个函数,根据直觉是可以构造出来的……
仿照上面的证明方法来构造:
设一个元素xx排名为第pp大,
那么有只有不包含比它小的n−p+1n-p+1个元素时,min⁡(T)=x\min(T)=x,有p−1p-1个元素可供随意选择,而且必然选择xx。
贡献系数是∑i=1p−1(p−1i)F(i+1)\sum\limits_{i=1}^{p-1}\dbinom{p-1}{i}F(i+1)。
我们要令这个=[p=k]=[p=k],也就是∑i=1p(pi)F(i+1)=[p=k−1]\sum\limits_{i=1}^{p}\dbinom{p}{i}F(i+1)=[p=k-1]
接下来使用二项式反演,还不会的同学请见“炫酷反演魔术”。
二项式反演得到 F(p+1)=∑i=1p(−1)p−i(pi)[i=k−1]=(−1)p−k+1(pk−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)=∑i=1p(−1)p−i(pi)[i=k−1]=(−1)p−k(p−1k−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)=∑T⊆S(−1)∣T∣−k(∣T∣−1k−1)min⁡(T)Kth\!\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min(T)
我们带入k=1k=1的情况,发现1th ⁣max⁡(S)=∑T⊆S(−1)∣T∣−1(∣T∣−10)min(T)=∑T⊆S(−1)∣T∣+1min⁡(T)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))=∑T⊆S(−1)∣T∣−k(∣T∣−1k−1)E(min⁡(T))E(Kth\!\max(S))=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))
题意:每秒按固定概率出现物品,求收集到 kk 个物品的期望时间。
这道题还是很有难度的,这个黑牌不亏(或者是我的dp太菜了……)
分析:我们设集合 SS 为某些物品的集合,物品的权值为第一次出现时间。
那么 E(min⁡(S))E(\min(S)) 就是这些物品中有其中一个出现的期望时间。
每一次得到 SS 中物品的概率是 ∑i∈Spi\sum\limits_{i∈S}p_i,那么期望时间就是1∑i∈Spi\dfrac{1}{\sum\limits_{i∈S}p_i}。
我们能求 E(min⁡(S))E(\min(S)) 了,我们再想想, E(Kth ⁣min⁡(U))E(Kth\!\min(U)) ( UU 是全集)不就相当于期望耗时吗?
我们令下文的 k=n−k+1k=n-k+1 ,求的就是 E(Kth ⁣max⁡(U))E(Kth\!\max(U)) 了,同时在题目中看到,这里的 k<=11k<=11 。
套用上面的扩展Min-Max容斥,我们就得到了式子:
Ans=∑T⊆S(−1)∣T∣−k(∣T∣−1k−1)E(min⁡(T)){\rm Ans}=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))
但是这里的 n≤1000n\leq 1000 不能直接O(2n)O(2^n)统计……
我们观察发现, m<=10000m<=10000 ,一道数数题居然限制值域? 没准是复杂度和 mm 有关的 dpdp。
这个 dpdp 十分复杂,具体过程就不放在这里了,其余请见 题解 P4707 【重返现世】

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

总结:
Min-Max容斥,考察范围较窄,学过的基本一眼就能看出来(flag)
但是可以结合期望,集合求和dp优化或者容斥,二项式反演来考,所以难度还是挺大的。
况且近年来都喜欢出毒瘤数数题,这玩意以后可能会被出成没有这么模板的题目吧,期待ing~

评论

共 58 条评论，欢迎与作者交流。

正在加载评论...