【BZOJ4036】[HAOI2015]按位或
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.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
Sample Output
2.6666666667
HINT
对于100%的数据，n<=20
题解：先判无解。然后进行fwt。对于每一项p，一次操作变成p的概率是$p$，两次是$p^2$，三次是$p^3$...所以期望次数就是$p\over (p-1)$。特别地，$2^n-1$的p=1，因为它不需要操作所以次数为0。再fwt回去即可。
手写小数读入优化炸精度调了半个小时~再也不写小数读入优化了~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
const int maxn=(1<<20)+4;
const db eps=1e-7;
db f[maxn],g[maxn];
bool vis[30];
int n;
db rd()
{
db ret=0,tmp=0.1; char gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
if(gc=='.')
{
gc=getchar();
while(gc>='0'&&gc<='9') ret=ret+(gc-'0')*tmp,tmp/=10,gc=getchar();
}
return ret;
}
inline void fwt(db *a)
{
int i,h;
for(h=0;h<n;h++) for(i=0;i<(1<<n);i++) if((i>>h)&1) a[i]+=a[i^(1<<h)];
}
inline void ufwt(db *a)
{
int i,h;
for(h=0;h<n;h++) for(i=0;i<(1<<n);i++) if((i>>h)&1) a[i]-=a[i^(1<<h)];
}
int main()
{
n=rd();
int i,j;
for(i=0;i<(1<<n);i++)
{
scanf("%lf",&f[i]);
if(f[i]>0) for(j=0;j<n;j++) if((i>>j)&1) vis[j]=1;
}
for(j=0;j<n;j++) if(!vis[j])
{
puts("INF");
return 0;
}
fwt(f);
for(i=0;i<(1<<n);i++)
{
if(i==(1<<n)-1) f[i]=0;
else f[i]=f[i]/(f[i]-1);
}
ufwt(f);
printf("%.10lf",f[(1<<n)-1]+1);
return 0;
}//2 0.25 0.25 0.25 0.25