[BZOJ 4036] 按位或

题目传送-BZOJ4036

题意：

刚开始你有一个数字(0)，每次给这个数按一定概率(or)上一个(le 2^n-1)的非负整数，概率(a)给定，保证和为1
问这个数字到(2^n-1)的期望(or)次数
(nle 20)

题解：

emmm见国家集训队2015论文集。。。

过程：

一切顺利

代码：

const int BIT=20,N=(1<<BIT)+10;
db p[N];
int bit,n;
inline void FWT(db *p,int n,int type) {
	// for(int i=0;i<n;i++) printf("%lf ",p[i]);
	for(int haf=1;haf<n;haf<<=1) {
		int len=haf<<1;
		for(int st=0;st<n;st+=len)
			for(int i=0;i<haf;i++)
				p[i+st+haf]+=p[st+i]*type;
	}
}
signed main() {
	read(bit); n=1<<bit;
	for(int i=0;i<n;i++) scanf("%lf",&p[i]);
	FWT(p,n,1);
	for(int i=0;i<n;i++) p[i]=1.0/(1.0-p[i]);
	p[n-1]=0;
	FWT(p,n,-1);
	p[n-1]=-p[n-1];
	if(p[n-1]<1e100) printf("%.10lf",p[n-1]);
	else puts("INF");
	return 0;
}

用时：15min