Problem
刚开始你有一个数字 \(0\)，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（C++,C 的 |，pascal 的 or）操作。选择数字 \(i\) 的概率是 \(p_i\)。保证 \(0\leq p_i \leq 1\)，\(\sum p_i=1\) 。问期望多少秒后，你手上的数字变成 \(2^n-1\)。
Solution（\(\min-\max\) 反演）
这个“或”是吓人的，我们可以等价地改为：有 \(n\) 个元素，每次从全集里选出一个子集并与手上原本为空的集合取并集，问手上什么时候取到全集。
考虑分离每一个元素进行考虑。设在某一种方案中，第 \(i\) 个元素第一次被加入手中的时间戳是 \(t_i\)，那么这一次手上取得全集的时间就是 \(\max t_i\)。那么我们要求的就是 \(E[\max t_i]\)。
根据 \(\min-\max\) 反演公式：（证明见后）
\[\max S=\sum_{T\subseteq S}(-1)^{|T|+1}\min T
\]
\[E[\max S]=\sum_{T\subseteq S}(-1)^{|T|+1}E[\min T]
\]
所以我们可以枚举子集，分别算出 \(E[\min T]\)，带个容斥系数求和。
好了现在我们有一个 \(E[\min T]\) 也就是 \(E[\min_{x\in T}t_x]\) 了，它表示 \(T\) 这个集合中的元素，任意一个第一次被染到的期望次数。
那么有一个 trick：做一件事情成功的概率如果是 \(p\)，那么我期望做成功的次数为 \(1/p\)。（一个骰子有六面，欲投出 \(6\)，是不是期望投 \(6\) 次？）严格证明
那么我们想要求概率。考虑这件事情的反面，选了一个完全无关的子集，的概率和很好算（高维前缀和）。于是就做完了。
code
点击查看代码
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define popcount __builtin_popcount
typedef long long LL;
int n;
double p[1<<20];
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=0;i<1<<n;i++) scanf("%lf",&p[i]);
for(int i=0;i<n;i++){//高维前缀和
for(int S=0;S<1<<n;S++){
if(S&(1<<i)) p[S]+=p[S^(1<<i)];
}
}
int U=(1<<n)-1;
double ans=0;
for(int S=1;S<1<<n;S++){
double ES=1/(1-p[U^S]);
if(fabs(1-p[U^S])<=1e-7) return puts("INF"),0;
debug("E[%d]=%.12lf\n",S,ES);
ans+=(popcount(S)&1?1:-1)*ES;
}
printf("%.12lf\n",ans);
return 0;
}
Proof of \(\min-\max\) 反演
\[\max S=\sum_{T\subseteq S}(-1)^{|T|+1}\min T
\]
\[\min S=\sum_{T\subseteq S}(-1)^{|T|+1}\max T
\]
假设元素互不相同。对于每个元素，设它从小到大的排名为 \(k\)。
- \(k=n\)：这个元素（叫作 \(a\)）是 LHS，对于右式来说只有一个集合 \(\{a\}\) 的 \(\min\) 是它，系数恰好为 \(1\)。
- \(k<n\)：这个元素不应该被计算，考虑它怎么被算的：肯定是后 \(n-k\) 个元素的子集并上它自己。那么考虑这其中有 \(2^{n-k-1}\) 个集合大小为奇数，\(2^{n-k-1}\) 个集合大小为偶数，那么它们全部被消除。
Qed.