DDOSvoid's Blog

Luogu P3175 [HAOI2015]按位或

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3175

简要题意：刚开始你有一个数字 $0$，给定一个整数 $n$ 以及 $[0,2^n-1]$ 的每个数字生成的概率，每秒随机生成一个数字与手上的数字或，问期望多少秒手上的数字变为 $2^n-1$

$n\le 20$

Solution

我们考虑 $min-max$ 容斥，我们另一个数字的大小表示它出现的时间

那么我们现在要求最大值 $\max_S$，我们发现这个东西不好求，我们考虑求最小值 $\min_S$

容易得到 $\min_S=\frac{1}{\sum_{T\cap S\neq \empty}p[T]}=\frac{1}{1-\sum_{T\subseteq (U-S)}p[T]}$，注意到这样的 $T$ 是 $S$​ 的补集的子集，也就是说我们只需要求一个高维前缀和即可

时间复杂度 $O(n2^n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <iomanip>
#define maxn 2000010
using namespace std;

const double eps = 1e-7;

int n, m;
double a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; m = (1 << n) - 1;
    for (int i = 0; i <= m; ++i) cin >> a[i];
    for (int o = 0; o < n; ++o)
        for (int S = 0; S <= m; ++S)
            if (S >> o & 1) a[S] += a[S ^ 1 << o];
    double ans = 0;
    for (int S = 1; S <= m; ++S) {
        int type = (__builtin_popcount(S) & 1) ? 1 : -1;
        if (1 - a[S ^ m] < eps) return cout << "INF" << "\n", 0;
        ans += type / (1 - a[S ^ m]); 
    } cout << fixed << setprecision(8) << ans << "\n";
    return 0;
}