Luogu3175 [HAOI2015]按位或

tony102

2021 年 09 月 07 日

1742 次浏览

暂无评论

467字数

题解

[Link](https://www.luogu.com.cn/problem/P3175)

## Sol

min-max 容斥题。还是利用了 min-max 容斥在期望下成立的性质。

现在要求的是：$E(max\{T\})$ 。但是好求的是 $E(min\{T\})$ 。这也是 min-max 容斥入门题的基本套路。有：

$$
E(min\{T\}) = \frac{1}{\sum\limits_{S\cap T \neq \emptyset} p(S)}
$$

只要任意一个 $S$ 与 $T$ 有交就至少会产生一个位。但是我不会。也许你会说，你会求超集。但是王总告诉你，对每一位取反后，就可以求子集。那么这个 $\sum$ 就可以用一个 FMT 预处理子集和解决。

然后就用这个式子套 min-max 容斥的基本式子就可以了。

## Code

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

const int SIZE = (1 << 20) + 5;
const double eps = 1e-7;

int n, m;
int cnt[SIZE];
double p[SIZE];

void FMT(double *a) {
	for (int a0 = 2, a1 = 1; a0 <= m; a0 <<= 1, a1 <<= 1)
		for (int i = 0; i < m; i += a0)
			for (int j = 0; j < a1; ++ j) a[i + j + a1] += a[i + j];
}

int main() {
	scanf("%d", &n); m = (1 << n);
	for (int i = 0; i < m; ++ i) scanf("%lf", &p[i]), cnt[i] += cnt[i >> 1] + (i & 1);
	FMT(p); double ans = 0.00;
	for (int i = 1; i < m; ++ i) {
		if (1.00 - p[(m - 1) ^ i] < eps) return puts("INF"), 0;
		ans += ((cnt[i] & 1) ? 1.00 : -1.00) / (1 - p[(m - 1) ^ i]);
	}
	printf("%.7lf\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 07 日