Bitwise XOR

题目描述

Given a sequence $a$ and an empty sequence $b$, each element in $a$ is added to $b$ with probability $P$ (independently to the other elements). Denote $s=\bigoplus_{i=1}^{|b|} b_i$, where $\oplus$ denotes bitwise xor and $s=0$ if $b$ is empty. Find the expected value of $s^2$.

题意概述

给定一个长度为$n$的序列$a$，其中每个数都有$P$的概率被选中。令被选中的数的异或和为$s$。求$s^2$的期望。

数据范围：$1 \le n \le 10^5, \ 0 \le a_i \lt 10^9+7$

算法分析

令$P(s)$表示异或和为$s$的概率。把$s$用二进制表示，最低位为第$0$位。

$$
\begin{align} \sum_s s^2P(s) &= \sum_s (\sum_{i=0}^{29} [s二进制第i位为1] 2^i)^2P(s) \\ &= \sum_s P(s) \sum_{i=0}^{29} [s二进制第i位为1] 2^i \sum_{j=0}^{29} [s二进制第j位为1] 2^j \\ &= \sum_s P(s) \sum_{i=0}^{29} \sum_{j=0}^{29} [s二进制第i位和第j位都为1] 2^{i+j} \\ &= \sum_{i=0}^{29} \sum_{j=0}^{29} P(s二进制第i位和第j位都为1) 2^{i+j} \end{align}
$$

先枚举$i$和$j$，令$f_{k,0/1,0/1}$表示从前$k$个数中选，异或和第$i$位、第$j$为分别为$0/1$、$0/1$的概率，对$f_{n,1,1}2^{i+j}$求和即为答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 100005, MOD = 1000000007;

int a[N], f[N][2][2];

int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}

int main() {
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    int p = 1ll * x * power(y, MOD - 2) % MOD, q = (MOD + 1 - p) % MOD;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int ans = 0, ans2 = 0;
    f[0][0][0] = 1;
    for (int i = 0; i < 30; ++i) {
        for (int j = i; j < 30; ++j) {
            for (int k = 1; k <= n; ++k) {
                for (int _i = 0; _i < 2; ++_i) {
                    for (int _j = 0; _j < 2; ++_j) {
                        int __i = _i ^ (a[k] >> i & 1);
                        int __j = _j ^ (a[k] >> j & 1);
                        f[k][_i][_j] = (1ll * f[k - 1][_i][_j] * q + 1ll * f[k - 1][__i][__j] * p) % MOD;
                    }
                }
            }
            ans = (ans + (1ll << i + j + (i != j)) % MOD * f[n][1][1]) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}