#P4036. [HAOI2015]按位或

    ID: 3237 传统题 2000ms 256MiB 尝试: 1031 已通过: 547 难度: 8 上传者: 标签>难度分类提高+/省选-组合数学容斥原理概率与期望尾和公式几何分布离线与分治分治算法构造与建模交换求和顺序数值计算与优化浮点补偿求和CF2400

[HAOI2015]按位或

题目描述

刚开始你有一个数字 00,每秒独立地从 00 到 2n−12^n-1 中按给定分布抽取一个整数,与你手上的数字进行或(C++,C 的 |,pascal 的 or)操作。选择数字 ii 的概率是 pip_i。保证 0≤pi≤10\leq p_i \leq 1,∑i=02n−1pi=1\sum_{i=0}^{2^n-1}p_i=1。问期望多少秒后,你手上的数字变成 2n−12^n-1。

输入格式

第一行输入整数 nn,表示二进制位数。第二行按顺序输入 2n2^n 个实数 p0,p1,…,p2n−1p_0,p_1,\ldots,p_{2^n-1},其中 pip_i 是抽到整数 ii 的概率。

输出格式

仅输出一个数表示答案,绝对误差或相对误差不超过 10−610^{-6} 即可算通过。如果目标永远无法达到,则输出 INF。

样例 #1

样例输入 #1

2
0.25 0.25 0.25 0.25

样例输出 #1

2.6666666667

数据范围

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