| 题目名称 | 1965. [HAOI 2015]按位或 |
|---|---|
| 输入输出 | haoi2015_set.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：54， 通过率：42.59% | ||||
 yrtiop |
100 | 1.232 s | 9.62 MiB | C++ |
 Imone NOI2018Au |
100 | 1.280 s | 8.68 MiB | C++ |
 荡漾 |
100 | 1.349 s | 15.57 MiB | C++ |
 iortheir |
100 | 1.401 s | 20.31 MiB | C++ |
 niconicoqaq |
100 | 1.417 s | 8.29 MiB | C++ |
 sxysxy |
100 | 1.422 s | 8.29 MiB | C++ |
 FoolMike |
100 | 1.446 s | 8.29 MiB | C++ |
 阿狸 |
100 | 1.566 s | 20.31 MiB | C++ |
 cstdio |
100 | 1.618 s | 20.31 MiB | C++ |
 mikumikumi |
100 | 1.631 s | 40.29 MiB | C++ |
| 关于 按位或 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
RP算法水过了。。。
疯狂卡常+迭代 O(N^2*logN) FWT暴力O(N*2^N)计算概率 大约只需要O(log(2^N))次迭代 clock()卡时。。。 | ||||
|
| ||||
|
手滑把n打成N竟然过了7个点
| ||||
|
回复 @Asm.Def :
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzz给烂大街跪 | ||||
|
Orz VFleaKing……Orz YDC……
（预感到CTSC之后这道题会烂大街，所以先来留个名……） 顺便给题解打个广告：http://www.cnblogs.com/Asm-Definer/p/4466729.html | ||||
__stdcall
Aglove
Asm.Def【题目描述】
刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行按位或（$C $和 $C++$ 的 $|$，$Pascal$ 的 $or$）操作。
选择数字 $i$ 的概率是 $p[i]$。保证 $0\le p[i]\le 1$，$\sum p[i]=1$。
问期望多少秒后，你手上的数字变成 $2^n-1$。
【输入格式】
第一行一个正整数 $n$。
第二行 $2^n$ 个实数，第 $i$ 个数表示选到 $i-1$ 的概率。
【输出格式】
一个数，表示答案。绝对误差或相对误差不超过 $10^{-6}$ 即可算通过。
如果无解要输出 $INF$
【输入样例1】
2 0.25 0.25 0.25 0.25
【输出样例1】
2.6666666667
【输入样例2】
2 1 0 0 0
【输出样例2】
INF
【数据范围】
对于 $30\%$ 的数据，$n\le 10$。
对于 $60\%$ 的数据，$n\le 15$。
对于 $100\%$ 的数据，$n\le 20$。