刚开始你有一个数字 $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$。
Min-Max容斥转化成求每个子集中任意取到一位的最早时刻
补集转化为一次取数不落在给定子集范围内的概率
FWT预处理
#include<iostream> #include<cstdio> using namespace std; int n,N,cnt[1050005]; double p[1050005],ans; inline int read() { int w=0,f=1; char ch=0; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)w=(w<<1)+(w<<3)+ch-‘0‘,ch=getchar(); return w*f; } int main() { n=read(),N=(1<<n)-1; for(int i=0;i<=N;i++) scanf("%lf",&p[i]),cnt[i]=cnt[i>>1]+(i&1); for(int i=1;i<=N;i<<=1) for(int j=0;j<=N;j+=2*i) for(int k=0;k<i;k++) p[i+j+k]+=p[j+k]; for(int i=1;i<=N;i++) if(1-p[N^i]>1e-10) if(cnt[i]&1) ans+=1/(1-p[N^i]); else ans-=1/(1-p[N^i]); else return puts("INF"),0; printf("%lf\n",ans); return 0; }
原文：https://www.cnblogs.com/JDFZ-ZZ/p/14197266.html
