526互联

min-max 容斥学习笔记

发布时间 2023-03-22 21:08:48作者: 曙诚

定义

设 \(\max(S)\) 为集合 S 中的最大值， \(\min(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) \]

对于 min-max 容斥，最简单的应用其实就是 $\min (a,b)=a+b-\max(a,b) $。

在一些题目中，如果题目要求的是最大值，但是直接求最大值比较困难，而求最小值很方便，那么就可以用到 min-max 的方式 \(O(2^n)\) 枚举子集容斥得出答案。

按位或

刚开始你有一个数字 \(0\)，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或操作。选择数字 \(i\) 的概率是 \(p_i\)。保证 \(0\leq p_i \leq 1\)，\(\sum p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\)。

\(n \leq 20\)。

思路

一个事实是，min-max 容斥定理在期望下也成立，记 \(E(\max(S))\) 为集合中 \(\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)) \]

在本题中，\(E(\max(S))\) 可以定义为 \(S\) 集合中最后一个变为 \(1\) 的数的期望时间，那么也就是 \(S\) 集合中全部变为 \(1\) 的期望时间，发现这个直接求是做不到的；而 \(E(\min(S))\) 就定义为 \(S\) 集合中第一个变为 \(1\) 的数的期望时间，而求这个就比较方便了。

令离散型随机变量 \(X\) 表示第一次变为 \(1\) 的时间，由高中概率相关的数学知识可以知道：

\[P(X=k)=(1-p)^{k-1} p \]

那么根据期望的定义，可以知道：

\[E(X)=\sum_{i=1}^{\infty} p(x=i)=\sum_{i=1}^{\infty} (1-p)^{i-1}p=p+(1-p)p+(1-p)^2p+\cdots+(1-p)^{\infty}p \]

不难发现这就是一个等比数列求和的式子，套用等比数列求和公式，可以得到：

\[E(X)=p \times \frac{1}{(1-(1-p))^2}=\frac{1}{p} \]

那么对于一个集合 \(T\) 来说，\(P_x\) 表示选到 \(x\) 这个数的概率，那么对于每次选择的数 \(G\)，只需要满足 \(G \cap T \ne \emptyset\) 就代表选到了这个集合，于是就有：

\[E(\min(T))=\frac{1}{P_T}=\frac{1}{\sum_{G \cap T \ne \emptyset} P_G}=\frac{1}{1-\sum_{G \cap T = \emptyset} P_G} \]

注意到 \(\sum_{G \cap T = \emptyset} P_G\) 实际上就是一个高维前缀和的形式，于是就可以用到 FWT。最后再套用一下 min-max 容斥即可得到答案。时间复杂度为 \(O(2^nn)\)。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1<<20;
const double eps=1e-8;
double p[N],ans;
int n,cnt[N];
void OR(double f[],int op)
{
	for(int i=0;i<n;i++)
	    for(int j=0;j<(1<<n);j++)
	        if((j>>i)&1) f[j]+=op*f[j^(1<<i)];
}
int main()
{
	scanf("%d",&n);for(int i=0;i<(1<<n);i++) scanf("%lf",&p[i]);OR(p,1);
	for(int i=0;i<(1<<n);i++) cnt[i]=cnt[i>>1]+(i&1);
	for(int i=1;i<(1<<n);i++)
	{
		if(1-p[((1<<n)-1)^i]<eps) continue;double val=1.0/(1-p[((1<<n)-1)^i]);
		if(cnt[i]&1) ans+=val;else ans-=val;
	}
	if(ans>eps) printf("%.10lf\n",ans);else puts("INF");
	return 0;
}