526互联

Min-Max 容斥学习笔记

发布时间 2023-10-01 17:27:51作者: Nityacke

前言

某次考试不会这个被打爆了，现在觉得可能有学习的必要。

Min-Max 容斥

我们现在有一个全集 \(U\)，设 \(\min(S)\) 为集合 \(S\) 中的最小值，\(\max(S)\) 为最大值。

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

然后这个有什么用捏，基本没用。
但是这个可以在期望下成立，即：

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

这个东西就很有用了，因为期望下的 \(\max,\min\) 可能比较难求一些。
证明可以利用期望的线性性。

然后这个东西还有拓展，比如求第 \(K\) 大。

\[Kthmax(S)=\min_{T\subseteq S}(-1)^{|T|+k}\binom{|T|-1}{k-1}\min(T)\\ Kthmin(S)=\min_{T\subseteq S}(-1)^{|T|+k}\binom{|T|-1}{k-1}\max(T)\\ E(Kthmax(S))=\min_{T\subseteq S}(-1)^{|T|+k}\binom{|T|-1}{k-1}E(\min(T))\\ E(Kthmin(S))=\min_{T\subseteq S}(-1)^{|T|+k}\binom{|T|-1}{k-1}E(\max(T))\\ \]

几何分布

离散随机变量就是一个随机变量只可以取一些特定的不连续值，比如全体正整数之类的。

如果有一个随机变量 \(X\)，\(p\) 为一个常量，而 \(k\in N^+\)，满足：

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

则称离散型随机变量 \(X\) 服从带参数 \(p\) 的几何分布。
然后这个东西的期望：

\[E(x)=\sum_{i=1}^\infty iP(x=i)\\ =p\sum_{i=1}^\infty i(1-p)^{i-1}\\ =p\frac 1 {1-(1-p^2)}=\frac 1 p \]

这个东西有什么用捏？等会就知道了。

例题

[HAOI2015]按位或

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

对于这个题，我们可以把每个二进制位分开考虑，若将每一个二进制位变成 \(1\) 当作全集 \(U\) ，则答案就是 \(E(\max(U))\)。

发现 \(\max\) 不好求，我们将答案转化成

\[\sum_{T\subseteq U}E(\min(T))(-1)^{|T|+1} \]

然后转化成求 \(E(\min(T))\)，\(E(\min(T))=\sum_{k=1}^\infty kP(\min(T)=k)\)。

而 \(P(\min(T)=k)\) 的意义就是前 \(k-1\) 次都选了这个集合补集的子集，第 \(k\) 次没选这个集合补集的子集。

我们令 \(P(S)\) 为选中 \(S\) 的子集的概率之和。

则 \(P(\min(T)=k)=P'(U\otimes T)^{k-1}(1-P'(U\otimes T))\)。

我们发现这就是几何分布的形式，所以 \(E(\min(T))=\frac 1 {P'(U\otimes T)}\)

然后对于求出 \(P'(S)\)，我们可以使用 FWT，然后这个题就做完了。

#include<bits/stdc++.h>
#define db double 
using namespace std;
const int N=(1<<20)+5;
const db eps=1e-10;
int n,tot,f[N];
db a[N],ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n,tot=1<<n;
	for(int i=0;i<tot;++i) cin>>a[i];
	for(int k=1;k<tot;k<<=1)
		for(int s=0;s<tot;s+=k<<1)
			for(int i=s;i<s+k;++i) a[i+k]+=a[i];
	f[1]=1;
	for(int i=2;i<tot;++i) f[i]=f[i>>1]*(i&1?-1:1);
	for(int i=1;i<tot;++i){
		if(1-a[(tot-1)^i]<eps) return cout<<"INF"<<endl,0;
		ans+=1/(1-a[(tot-1)^i])*f[i];
	}
	printf("%.10lf",ans);
}

某考试题

有 \(n\) 种卡，每种卡有 \(3\) 种颜色，每次抽卡最多可以抽到一张卡，每氪金一次可以连抽 \(m\) 次卡，前 \(m-1\) 次抽卡时抽到第 \(i\) 种卡的概率是 \(p_i\)，什么都抽不到的概率为 \(1-\sum p_i\)，而最后一次抽卡抽到第 \(i\) 张卡的概率是 \(q_i\)，什么都抽不到的概率为 \(1-\sum q_i\)，如果抽到了一张卡，是每种颜色的概率都是 \(\frac 1 3\)。询问期望要氪金多少次才能获得所有的卡。

\(1\le n\le 9,1\le m\le 64\)。

我们把每张卡拆成 \(3\) 张，分别代表每个颜色，然后每张卡抽中的概率就变成了 \(\frac {p_i} 3 ,\frac {q_i} 3\)，套用 Min-Max 容斥。

\[E(\max(U))=\sum_{T\subseteq U}(-1)^{|T|+1}E(\min(T))\\ \]

然后考虑如何求 \(E(\min(T))\)，一次氪金不中的概率为 \((1-\sum_{i\in T}p'_i)^{m-1}(1-\sum_{i\in T}q'_i)\)，即：

\[E(\min(T))=\frac 1 {1-(1-\sum_{i\in T}p'_i)^{m-1}(1-\sum_{i\in T}q'_i)} \]

然后我们就有了一个 \(O(2^{3n}(n+\log m+\log mod))\) 的做法，可能过不去。

我们把每种牌附上 \(4\) 种状态，有 \(0,1,2,3\) 种颜色。

然后对每个状态，我们可以套用上面的式子，但是要乘上一个 \(\binom{3}{k}\) ，\(k\) 为当前状态的颜色数量，然后就可以做到 \(O(4^n(n+\log m+\log mod))\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=25,mod=2000000011;
int p[N],q[N],n,m;
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
int a[N],C[N]={1,3,3,1},ans;
inline void add(int &x,int y){
	x=((x+y)%mod+mod)%mod;
}
inline void calc(int x){
	for(int i=1;i<=n;++i)
		a[i]=x%4,x>>=2;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>p[i],p[i]=p[i]*qpow(300*n,mod-2)%mod;
	for(int i=1;i<=n;++i) cin>>q[i],q[i]=q[i]*qpow(300*n,mod-2)%mod;
	int tot=1<<(2*n);
	for(int k=1;k<tot;++k){
		calc(k);
		int mul=1,sz=0,a1=0,a2=0;
		for(int i=1;i<=n;++i) sz+=a[i],mul=mul*C[a[i]]%mod;
		for(int i=1;i<=n;++i) add(a1,p[i]*a[i]%mod);
		for(int i=1;i<=n;++i) add(a2,q[i]*a[i]%mod);
		a1=(mod+1-a1)%mod,a2=(mod+1-a2)%mod;
		int res=mod+1;
		add(res,-qpow(a1,m-1)*a2%mod);
		res=qpow(res,mod-2)*mul%mod;
		if(sz&1) add(ans,res);
		else add(ans,-res);
	}
	cout<<ans<<endl;
}

可能还需要个例题，但是她鸽了