Description：

一个数字刚开始为 $0$ ，每次选择一个 $[0,2^n-1]$ 的数字，与当前的数字进行或操作。选择 $i$ 的概率是 $p[i]$ 。问期望多少次后，数字变成 $2^n-1$ 。

$1\leqslant n\leqslant 20$

Solution：

首先我们发现这一位一位之间是不独立的。

如果我们把这个二进制每一位分开来看，记每个数的权值为他变成一的期望次数，那么 $ans=E(\max(S))$ ，即 $S$ 中最大值的期望。

有一个叫做 $\min-\max$ 容斥的东西，也叫做最值反演，大概形式是： $$ \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(S)\\ \min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(S) $$

它的重要性在于可以把 $\max(或\min)$ 不好求的转化为 $\min(或\max)$ ，最重要的是，这个公式在期望下也成立，即： $$ E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T)) $$ 那么我们只要求出 $E(\min(T))$ 即可，也就是 $T$ 中有一位变成 $1$ 的最期望时间。

有一个东西叫做离散型随机变量的几何分布，含义是在 $n$ 次伯努利试验中，前 $k$ 次均失败，最后一次成功的概率，公式是： $P(x=k)=(1-p)^{k-1}p$ ，他的期望 $E(x)=\frac 1 p$ 。

那么对于这个显然是可以套这个模型的， $p=1-$ 选择了一个所有 $1$ 的位置都不在这个集合的概率，即： $$ p=\sum_{S'\subseteq\complement_ST}p[S'] $$ 这时我们发现只要求出了某个集合的所有子集的概率和，就可以套用 $\min-\max$ 容斥，求子集和可以用 $FMT$ 来 $O(n2^n)$ 做。

无解就是 $p[\complement_ST]=1$ ，即这个位置永远不会被选中。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 21

double p[1 << MAXN];

int cnt[1 << MAXN];

void FMT(double f[],int l)

{

	for(int i = 0;i < l;++i)

		for(int k = 0;k < (1 << l);++k)

			if((k >> i) & 1)f[k] += f[k ^ (1 << i)];

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 0;i < (1 << n);++i)scanf("%lf",&p[i]);

	for(int i = 0;i < n;++i)cnt[1 << i] = 1;

	FMT(p,n);

	for(int i = 0;i < (1 << n);++i)cnt[i] = cnt[i >> 1] + (i & 1);

	double ans = 0.0;

	int tot = (1 << n) - 1;

	for(int i = 1;i < (1 << n);++i)

	{

		if(fabs(1.0 - p[tot ^ i]) < 1e-6)

		{

			puts("INF");

			return 0;

		}

		ans += (1 / (1.0 - p[tot ^ i])) * ((cnt[i] & 1) ? 1 : -1);

	}

	printf("%.10lf\n",ans);

	return 0;

}