按位或

题目链接：luogu P3175

题目大意

有一个数 0 你一开始，然后每次你可以与上一个数 0~2^n-1 中的，每个数有它被你选择的概率。
然后问你期望要弄多少次才能使得这个数变成 2^n-1。

思路

首先这个弄成 /(2^n-1/) 显然不好弄，我们考虑一个神奇的东西，就是 min-max 容斥。
因为这个 /(/min,/max/) 它不一定要是最大值最小值，它可以是最早出现最晚出现之类的。
所以我们可以视作最后一次操作让 /(2^n-1/) 完成是最晚出现，那最早出现就是第一次开始拼 /(2^n-1/)。
那再看回去 min-max 容斥的式子：/(/max(T)=/sum/limits_{T/subset S}(-1)^{|S|}/min(S)/)

那我们就要求出每个子集第一次被覆盖到的期望时间，设为 /(f(S)/)。
考虑生成函数，对于每次如果覆盖到就结束，没有覆盖到就要继续，然后没有覆盖到相当于覆盖了 /(S/) 的补集（这里设为 /(nS/)）的子集，然后设一次操作选的集合是 /(S/) 的子集的概率为 /(P(S)/)。
/(f(S)=P(nS)f(S)+1/)
/(f(S)=/dfrac{1}{1-P(nS)}/)

然后再看怎么求 /(P(S)/)，这个其实简单，直接一个高位前缀和就好了。
不过后来发现也可以用 FWT 之类的。

就是好像是对于 FWT 的或，它是这样的：
/(C_i=/sum/limits_{j|k=i}A_jB_k/)
然后如果设 /(f(C_i)=/sum/limits_{j/subseteq i}C_j/)
那 /(f(C_i)=/sum/limits_{j|k/subseteq i}A_jB_k=/sum/limits_{j/subseteq i,k/subseteq i}A_jB_k=f(A_i)f(B_i)/)

那 FWT 不就是跟 FFT 差不多弄个变换然后逆变换吗？
那我们 FWT 或变换得到的就是子集和！

很神奇吧。

然后又一些细节，就是记得有个东西是如果无解输出 INF。
那首先如果答案是 /(0/) 你得 INF，而且可能因为你 /(f(S)/) 的求里面可能下面是 /(0/)（就 /(P(nS)=1/)），所以碰到这些你要直接跳过，不然会出问题。

代码

#include<cstdio>

using namespace std;

const int N = 20;
const double eps = 1e-8;
int n, xs[1 << N];
double p[1 << N], f[1 << N], ans;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < (1 << n); i++) scanf("%lf", &p[i]);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < (1 << n); j++)
			if ((j >> i) & 1) p[j] += p[j ^ (1 << i)];
	}
	
	xs[0] = -1;
	for (int i = 1; i < (1 << n); i++) {
		xs[i] = -xs[i ^ (i & (-i))];
		if (1 - p[i ^ ((1 << n) - 1)] < eps) continue;
		f[i] = 1.0 / (1 - p[i ^ ((1 << n) - 1)]);
		ans += f[i] * xs[i];
	}
	if (ans < eps) printf("INF");
		else printf("%.8lf", ans);
	
	return 0;
}