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

题意

　　刚开始你有一个数字 $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 
     
      using namespace std;const int N=1<<20;int n;double a[N];void FWT(double a[],int flag){	for (int d=1;d
      
       <<=1)		for (int i=0;i
       
        <<1))			for (int j=0;j