前言
某次考试不会这个被打爆了，现在觉得可能有学习的必要。
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)\\ \]然后这个有什么用捏，基本没用。
但是这个可以在期望下成立，即：
这个东西就很有用了，因为期望下的 \(\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\) 的几何分布。
然后这个东西的期望：
这个东西有什么用捏？等会就知道了。
例题
[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;
}
可能还需要个例题，但是她鸽了
标签：min,int,Max,sum,Min,容斥,max,subseteq,mod From： https://www.cnblogs.com/Nityacke/p/17738849.html