#2127. 「HAOI2015」按位或

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

刚开始你有一个数字 0 ,每一秒钟你会随机选择一个 [0,2^n-1] 的数字,与你手上的数字进行或(C++, C 的 |, Pascal 的 or)操作。选择数字 i 的概率是 p[i] (保证 0 \leq p[i] \leq 1, \ \sum p[i] = 1 ) 问期望多少秒后,你手上的数字变成 2^n-1

输入格式

第一行输入 n 表示 n 个元素,第二行输入 2^n 个数,第 i 个数表示选到 i-1 的概率。

输出格式

仅输出一个数表示答案,绝对误差或相对误差不超过 10^{-6} 即可算通过。如果无解则要输出INF

样例

样例输入

2
0.25 0.25 0.25 0.25

样例输出

2.6666666667

数据范围与提示

对于 100 \% 的数据, n \leq 20