C++(clang++11) 解法, 执行用时: 324ms, 内存消耗: 8596K, 提交时间: 2020-11-12 23:48:10

#include<cstdio>
#include<cmath>
using namespace std;
const int N = (1 << 21) + 5;
double p[N];
inline void fwtor(int n, double f[], int inv = 1){
	int i, j, k;
	for(k = 1;k < n;k <<= 1)
		for(i = 0;i < n;i += k << 1)
			for(j = 0;j < k;j++)
				f[i + j + k] += inv * f[i + j];
}
int main(){
	int n, i;
	scanf("%d", &n);n = 1 << n;
	for(i = 0;i < n;i++)scanf("%lf", &p[i]);
	fwtor(n, p);
	for(i = n - 2, p[n - 1] = 0;i >= 0;i--){
		if(abs(p[i] - 1) < 1e-6)break;
		p[i] = 1 / (p[i] - 1);
	}if(i >= 0)printf("INF");
	else{
		fwtor(n, p, -1);
		printf("%.10lf", p[n - 1]);
	}
	return 0;
}