原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ4036.html

题目传送门 - BZOJ4036

题意

　　刚开始你有一个数字 $0$ ，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行 $OR$ (按位或) 操作。

　　选择数字 $i$ 的概率是 $p_i$ 。保证 $0\leq p_i\leq 1$ ，$\sum_{i=0}^{2^n-1}p_i=1$ 。

　　问期望多少秒后，你手上的数字变成 $2^n-1$ 。

　　$n\leq 20$

题解

　　先 FWT 一下 。

　　我们称状态 $x$ 为当前停留在 $x$ 的子集中。

　　对于状态 $x$ ，每一次停留在 $x$ 的概率为 $p_x$ 。

　　所以每一步走出 $x$ 的概率就是 $1-p_x$ 。

　　所以走出 $x$ 的期望步数为 $\cfrac{1}{1-p_x}$ 次。

　　显然走出 $2^n-1$ 的期望步数为 $\infty$ 。

　　但是走入 $2^n-1$ 的期望步数为走出所有其他状态的期望步数。

　　所以 UFWT 的结果是负的“走入 $2^n-1$ 的期望步数" 。

　　于是判一判就可以了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1<<20;

int n;

double a[N];

void FWT(double a[],int flag){

	for (int d=1;d<n;d<<=1)

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

			for (int j=0;j<d;j++)

				a[i+j+d]+=a[i+j]*flag;

}

int main(){

	scanf("%d",&n),n=1<<n;

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

		scanf("%lf",&a[i]);

	FWT(a,1);

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

		a[i]=1.0/(1.0-a[i]);

	a[n-1]=0;

	FWT(a,-1);

	a[n-1]=-a[n-1];

	if (a[n-1]<1e100)

		printf("%.8lf",a[n-1]);

	else

		puts("INF");

	return 0;

}