首页 > 其他 > 详细

BZOJ4036:按位或 (min_max容斥&FWT)(占位)

时间:2018-11-12 17:19:47      阅读:272      评论:0      收藏:0      [点我收藏+]

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;
}

 

BZOJ4036:按位或 (min_max容斥&FWT)(占位)

原文:https://www.cnblogs.com/hua-dong/p/9947024.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!