Description
刚开始你有一个数字 0, 每一秒钟你会随机选择一个 [0,2^n-1] 的数字, 与你手上的数字进行或(c++,c 的 |,pascal
的 or)操作. 选择数字 i 的概率是 p[i]. 保证 0<=p[i]<=1,Σp[i]=1 问期望多少秒后, 你手上的数字变成 2^n-1.
Input
第一行输入 n 表示 n 个元素, 第二行输入 2^n 个数, 第 i 个数表示选到 i-1 的概率
Output
仅输出一个数表示答案, 绝对误差或相对误差不超过 1e-6 即可算通过. 如果无解则要输出 INF
- Sample Input
- 2
- 0.250.250.250.25
- Sample Output
- 2.6666666667
- HINT
对于 100% 的数据, n<=20
思路: 可以 min_max 容斥来做, 问题的关键就是求出得到所有子集 X 的期望 F(X)就可以了, P(X)的概率为所有对 X 有贡献的 p[x]之和(x 是所有和 X 有交集的 x, 即便 x 含有 X 没有的部分);
我们倒过来求与 X 交集为空的部分的概率, 这部分可以用高维前缀和来做. 高维前缀和这里还没见到过, 占位. 代码先码了.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1<<21;
- double P[maxn],ans;int N,sum,M;
- void dfs(int pos,int now,int cnt)
- {
- if(pos==N){
- if(cnt>=1){
- if(cnt&1) ans+=1.0/(1.0-P[(M-1)^now]);
- else ans-=1.0/(1.0-P[(M-1)^now]);
- }
- return ;
- }
- dfs(pos+1,now|(1<<pos),cnt+1);
- dfs(pos+1,now,cnt);
- }
- int main()
- {
- scanf("%d",&N); M=1<<N;
- for(int i=0;i<M;i++){
- scanf("%lf",&P[i]);
- if(P[i]>0) sum|=i;
- }
- if(sum!=M-1) return puts("INF"),0;
- for(int i=1;i<M;i<<=1)
- for(int p=i<<1,j=0;j<M;j+=p)
- for(int k=0;k<i;++k)
- P[i+j+k]+=P[j+k];
- dfs(0,0,0);
- printf("%.6lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2844149.html