$Min-Max$ 容斥定理在期望条件下也是成立的。
直接套用 $Min-Max$ 容斥。
子集和就直接用 $or$ 的 $DWT$ 就好了。
代码巨短。
#include<bits/stdc++.h>
using namespace std;
const int N=21;
const double eps=1e-9;
int n;
double a[1<<N],ans;
int count1(int x) {
int ans=0;
while(x) ans+=x&1,x>>=1;
return ans;
}
int main() {
scanf("%d",&n);
for(int i=0;i<1<<n;i++) scanf("%lf",&a[i]);
for(int mid=1;mid<1<<n;mid<<=1)
for(int i=0;i<1<<n;i+=mid<<1)
for(int j=0;j<mid;++j) a[i+j+mid]+=a[i+j];
for(int i=0;i<(1<<n)-1;++i) {
if(1-a[i]<eps) {
puts("INF");
return 0;
}
a[i]=1./(1-a[i]);
}
for(int i=1;i<1<<n;++i) ans+=((count1(i)&1)?1.:-1.)*a[i^((1<<n)-1)];
printf("%.12lf",ans);
return 0;
}