题目描述
刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行位或 (即c++中的 '|' ) 操作。
选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。
输入输出格式
输入格式：
第一行输入n表示n个元素，第二行输入2^n个数，第i个数表示选到i-1的概率
输出格式：
仅输出一个数表示答案，绝对误差或相对误差不超过1e-6即可算通过。如果无解则要输出INF
输入输出样例
说明
对于100%的数据，n<=20
可以说是FMT的板子了，虽然如果你光是背的话是做不出来的hhhh，而且还需要一点期望的知识。
设i秒后数字是 2^n - 1 的概率是 q[i] ，注意 i-1秒 的 2^n - 1 也同样可以转移到 i 秒 的 2^n - 1。
那么答案就显然了：Σ i * (q[i] - q[i-1])。
但是问题随之而来：这个玩意是不是无穷大的啊，毕竟 都有 q[i] > q[i-1] ,且i可以是正无穷啊？
但实际上这个玩意是收敛的，考虑i很大的时候，q[i] - q[i-1] 趋近于0，就没有贡献了。
但是这个玩意怎么算啊qwq
先考虑一个简单的问题：如果是求q[i]的话我们怎么求？
这个比较简单，就是把 p[] 数组 自己卷 i 次，然后 p[2^n - 1]就是 q[i] 啦。。。
卷？？ 当然还得定义乘法，这里的集合乘法 就是 位或 (or) ，所以如果单独求 q[x] 的话 ，就是FMT的板子啦。。。
但是这个题求的是一坨子q[x]带权加起来，，，这可咋办啊？？
伟大的vfleaking先辈已经在他的论文里告诉了我们，对一个形式幂级数 进行 加减乘除 操作 就相当于 对它的 莫比乌斯变换 进行加减乘除操作。
而莫比乌斯变换可以把原形式幂级数的卷积直接变成乘法。。。然后这就是个等差+等比数列求和的问题了，请自行手玩hhhh
/*
(p - 1) + 2*(p^2 - p) + 3*(p^3 - p^2) + ....
= 1/(p-1) (0<p<1) or 0 (p==1)
*/
#include<bits/stdc++.h>
#define ll long long
const int maxn=1100005;
#define D double
using namespace std;
const D eps=1e-9;
int N,ci[35];
D f[maxn];
inline void FMT(int F){
for(int i=0;i<N;i++)
for(int j=ci[N]-1;j>=0;j--) if(!(ci[i]&j)) f[ci[i]|j]+=F*f[j];
}
int main(){
ci[0]=1; for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;
scanf("%d",&N);
for(int i=0;i<ci[N];i++) scanf("%lf",f+i);
FMT(1),f[ci[N]-1]=0;
for(int i=ci[N]-2;i>=0;i--){
if(1-f[i]<eps){
puts("INF");
return 0;
}
f[i]=1/(f[i]-1);
}
FMT(-1);
printf("%.11lf
",f[ci[N]-1]);
return 0;
}