[HAOI2015] 按位或

世界是物质的，物质是运动的，运动是有规律的，规律是可以被认识的。

期望意义的最值反演

[E(max S)=sum_{Tsubseteq S}(-1)^{|T|-1}E(min T) ]

其中(E(max S))，(E(min S))分别表示(S)中所遇事件全部出现和至少出现一个的期望。

故答案为

[sum_{T}(-1)^{|T|-1}frac1{1-sum_{Xsubseteq complement_uT} P(X)} ]

子集和的那部分直接高维前缀和即可。

No emptyset

#include <bits/stdc++.h>
using namespace std;

int n,len;
double p[1<<20];

int main() {
	scanf("%d",&n);
	len=1<<n;
	for(int i=0; i<len; ++i)
		scanf("%lf",p+i);
	for(int i=0; i<n; ++i)
		for(int j=0; j<len; ++j) 
			if((j>>i)&1)
				p[j]+=p[j^(1<<i)];
	double ans;
	for(int i=1; i<len; ++i) 
		if(1-p[(len-1)^i]<1e-9) {
			puts("INF");
			return 0;
		}
		else 
			ans+=(__builtin_popcount(i)&1?1:-1)*1/(1-p[(len-1)^i]);
	printf("%.8f
",ans);
	return 0;
}