Description

刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行或（c++,c的|,pascal的or）操作。

选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。

Solution

相当于给你一个集合求最后一个元素出现的时间

可以用\(minmax\) 容斥一波，这样就是求每个子集中第一个元素出现的时间\(min(T)\)啦

我们设\(P(T)\)表示取到\(T\)的子集的概率

\[ P(min(T)==k)=P(S-T)^{k-1}(1-P(S-T)) \]

然后因为：

\[ 若P(x==k)=(1-p)^{k-1}p(k \in N^{+})，则E(x)=\frac{1}{p} \]

所以：

\[ E(min(T))=\frac{1}{1-P(S-T)} \]

问题在于，如何求\(P(T)\)呢

显然

\[ P(T)=\sum_{x⊆T}p(x)，这里我们把一个数都当作一个集合，p(x)就是题目给出的得到x的概率 \]

求子集和？可以用像 一样的子集和dp，当然，也可以直接\(FWT\)变换一下。

Code 

#include
    
     #define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))int n,N,num[1<<20];double P[1<<20],Ans=0.;int main(){    scanf("%d",&n);N=1<
     
      >1]+(i&1);        if(1-P[(N-1)^i]<1e-9) return 0*puts("INF");        Ans+=((num[i]&1)?1.:-1.)*(1./(1.-P[(N-1)^i]));    }    printf("%.9lf\n",Ans);    return 0;}
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！