首先这种跟二进制位有关的期望题很显然就是考虑Min-Max容斥。
这道题的集合显然就是所有二进制位。
于是E(max(S))=∑T⊆S(−1)∣T∣+1E(min(T))E(\max(S))=\sum_{T\subseteqS}(-1)^{|T|+1}E(\min(T))E(max(S))=T⊆S∑(−1)∣T∣+1E(min(T))
显然TTT集合中的元素期望最早时间出现就是1∑U∩T!=∅PU\dfrac{1}{\sum\limits_{U\capT!=\empty}P_U}U∩T!=∅∑PU1
我们需要求所有和一个集合交不为空的集合的PPP之和。
转化为求所有和一个集合交为空的集合的PPP之和，发现就是该集合补集的所有子集，直接用快速莫比乌斯变换就行了。
代码：
#include<bits/stdc++.h>#definelllonglong#definereregister#definegcget_char#definecsconstnamespaceIO{inlinecharget_char(){staticcsintRlen=1<<22|1;staticcharbuf[Rlen],*p1,*p2;return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}inlinedoublegetdb(){charc;while(!isdigit(c=gc()));doublex=c^48;while(isdigit(c=gc()))x=(x*10)+(c^48);if(c!='.')returnx;doubley=1;while(isdigit(c=gc()))x+=(y/=10)*(c^48);returnx;}}usingnamespaceIO;usingstd::cerr;usingstd::cout;csintN=1<<20|1;doublea[N];intpopcount[N];signedmain(){#ifdefzxyoifreopen("or.in","r",stdin);#endifintlen;scanf("%d",&len);len=1<<len;intok=0;for(intrei=0;i<len;++i)a[i]=getdb(),popcount[i]=popcount[i>>1]^(i&1);for(intrei=0;i<len;++i)if(a[i]>1e-6)ok|=i;if(ok!=len-1)puts("INF"),exit(0);for(intrei=1;i<len;i<<=1)for(intrej=0;j<len;j+=i<<1)for(intrek=0;k<i;++k)a[i|k|j]+=a[k|j];doubleans=0;for(intrei=1;i<len;++i){doubleval=1/(1-a[(len-1)^i]);popcount[i]?ans+=val:ans-=val;}printf("%.12f",ans);return0;}
