洛谷P3175 [HAOI2015]按位或

zrzring 2021-01-26 PM 43℃ 0条

题目可以转化为给定每种集合触发概率,问期望多少次可以触发全集,用$E(max(S))$表示集合$S$中最晚出现元素出现时间的期望,根据min-max容斥

$$ E(max(S)) = \sum_{S'\subseteq S} (-1)^{|S'|} \times E(min(S')) $$

如何计算$E(min(S))$,记$S$的补集为$R$,每次$S$集合中的元素被选中的概率为

$$ \sum_{T\cap S\not = \varnothing}P(T) = 1 - \sum_{T\cap S = \varnothing}P(T) = 1 - \sum_{T\subseteq R}P(T) $$

可以用FMT计算,若一个事件发生的概率为$p$,该事件期望重复$E$次可以发生,则有

$$ E = \sum_{i\geq 1} i(1 - p)^{i - 1}p = p\sum_{i\geq 1} i(1 - p)^{i - 1} $$

内部是个等差数列乘一个等比数列,根据套路错位相减

$$ \begin{aligned} S = \sum_{i\geq 1} i(1 - p)^{i - 1}\\ (1 - p)S = \sum_{i\geq 1} i(1 - p)^{i}\\ pS = 1 + \sum_{i\geq 1}(1 - p)^i \end{aligned} $$

根据等比数列求和公式,得出$\displaystyle E = \frac{1}{p}$,于是

$$ E(min(S)) = \frac{1}{1 - \sum_{T\subseteq R}P(T)} $$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);

using namespace std;

const int N = 2e6 + 10;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, m, cnt[N];

double P[N];

int main() {
    n = 1 << read();
    for (int i = 0; i < n; i++) scanf("%lf", &P[i]), cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = j; k < j + i; k++) P[k + i] += P[k];
        }
    }
    double ans = 0;
    for (int i = 1; i < n; i++) {
        if (1 - P[n - 1 ^ i] > 1e-10) ans += (cnt[i] & 1 ? 1 : -1) / (1 - P[n - 1 ^ i]);
    }
    if (ans <= 1e-10) printf("INF"); else printf("%.10lf", ans);
    return 0;
}
Title - Artist
0:00