BZOJ4036 按位或

vfk 论文上的一道例题

题意

给出 $n$ ,每秒会有 $p_i$ 的概率选择 $i ,i \in [0, 2^n – 1]$ ,与手上的数进行异或,问期望多少次后手上的数会变成 $2^n-1$

题解

果然还是应该用 $\hat f$ 来表示 $f$ 的莫比乌斯变换,不然我整个人都比较懵
设 $f_i$ 表示操作 $i$ 次后得到数字的概率的生成函数, $U$ 为 $2^n – 1$
设 $h_S$ 表示得到 $S$ 的期望操作次数,将 $f$ 看成集合幂级数,则
$$ h_S = \sum_{k=1}^{\infty} k\cdot(f^k – f^{k-1}) $$

做莫比乌斯变换
$$ \hat h_S = \sum_{k=1}^{\infty} k\cdot (\hat f_S^k – \hat f_S^{k-1}) $$
通过扰动法W|A可以得到
image.png
于是有
$$\hat h_S = \frac{1}{\hat f_S – 1},\hat f_S < 1$$
将 $f$ 反演得到 $\hat f$ 后转换成 $\hat h$ 然后再快速反演回 $h$ 就有答案了

代码

#define MAX_N 2000007

int N;
double p[MAX_N];

inline void FWT (double *A, int M, int type) {
    for (int l = 1; l < M; l <<= 1) {
        for (int i = 0; i < M; i += (l << 1)) {
            for (int j = i, x, y; j < i + l; ++j) {
                A[j + l] += A[j] * type;
            }
        }
    }
}

int main () {
    int x;
    read(x); N = 1 << x;
    int U;
    for (int i = 0; i < N; ++i) {
        scanf("%lf", p + i);
        if (p[i])
            U |= i;
    }
    if (U < N - 1) return puts("INF"), 0;
    FWT(p, N, 1);
    for (int i = 0; i < N - 1; ++i)
        p[i] = 1.0 / (p[i] - 1.0);
    p[N - 1] = 0;
    FWT(p, N, -1);
    printf("%.8lf\n", p[N - 1]);
    return 0;
}

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注