Min-Max容斥小记

广告 : [炫酷反演魔术](https://www.luogu.com.cn/blog/command-block/xuan-ku-fan-yan-mo-shu) 这个东西看起来挺冷门的，不过要是考的话到不会还真做不出来…… 这东西也不是很复杂，本文应该不会太长吧…… 我们现在有一个全集 $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]按位或](https://www.luogu.org/problemnew/show/P3175) 第一眼看去很难把这道题和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的，所以请使用[位运算卷积](https://www.luogu.org/blog/command-block/wei-yun-suan-juan-ji-yu-ji-kuo-zhan) $Or$ 卷积的 $DWT$ 相当于子集求和,那么直接上就好了。 ```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; } ``` - **扩展形式** 如果要求第$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 重返现世](https://www.luogu.org/problemnew/show/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)$统计…… 我们观察发现, $m<=10000$ ,一道数数题居然限制值域? 没准是复杂度和 $m$ 有关的 $dp$。 这个 $dp$ 十分复杂,具体过程就不放在这里了,其余请见 [题解 P4707 【重返现世】](https://www.luogu.org/blog/command-block/solution-p4707) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- ------------ **总结:** Min-Max容斥,考察范围较窄,学过的基本一眼就能看出来(flag) 但是可以结合期望,集合求和dp优化或者容斥,二项式反演来考,所以难度还是挺大的。 况且近年来都喜欢出毒瘤数数题,这玩意以后可能会被出成没有这么模板的题目吧,期待ing~