记录编号	446500	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]按位或	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	1.280 s
提交时间	2017-09-08 14:45:14	内存使用	8.68 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
const double eps = 1e-12;
using namespace std;

inline void read(int &x) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '9'));
	x = ch - '0'; while((ch = getchar()), (ch >= '0' && ch <= '9')) x = x * 10 + (ch  - '0');
}
inline void floatread(double &x) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '9')); x = ch - '0';
	ch = getchar(); if(ch != '.') return;
	double val = 0.1; while((ch = getchar()), (ch >= '0' && ch <= '9')) x += val * (ch - '0'), val /= 10;
}
inline void fmt(double A[], int n) {
	int h, i;
	for(h = 0; h < n; h++) for(i = 0; i < (1 << n); i++) if((i >> h) & 1) A[i] += A[i ^ (1 << h)];
}
inline void ifmt(double A[], int n) {
	int h, i;
	for(h = 0; h < n; h++) for(i = 0; i < (1 << n); i++) if((i >> h) & 1) A[i] -= A[i ^ (1 << h)];
}

const int MAXN = 20;
int N;
double A[(1 << MAXN) + 5];
bool bit[MAXN + 5];

int main() {
	freopen("haoi2015_set.in", "rt", stdin);
	freopen("haoi2015_set.out", "wt", stdout);

	int i, k; read(N);
	for(i = 0; i < (1 << N); i++) {
		floatread(A[i]); if(A[i] >= eps) for(k = 0; k < N; k++) if((i >> k) & 1) bit[k] = 1;
	}
	for(i = 0; i < N; i++) if(!bit[i]) { printf("INF"); return 0; }

	fmt(A, N);
	for(i = 0; i < (1 << N); i++) {
		if(fabs(A[i] - 1.0) <= eps) A[i] = 0;
		else A[i] = -1.0 / (1.0 - A[i]);
	}
	ifmt(A, N);
	printf("%.8lf", A[(1 << N) - 1]);
}