CF2020E.Expected Power

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$，以及一个数组 $p_1, p_2, \ldots, p_n$。

定义随机多重集 $S$（即 $S$ 可以包含相同元素），其构造方式如下：

• 初始时，$S$ 为空集。
• 对于每个 $i$ 从 $1$ 到 $n$，以概率 $\frac{p_i}{10^4}$ 将 $a_i$ 插入 $S$。注意，每个元素是否被插入是独立的。

记 $f(S)$ 为 $S$ 中所有元素的按位异或（bitwise XOR）结果。请计算 $\mathbb{E}[(f(S))^2]$ 的期望值，并将答案对 $10^9 + 7$ 取模输出。

形式化地，设 $M = 10^9 + 7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 1023$）。

第三行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1 \le p_i \le 10^4$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $\mathbb{E}[(f(S))^2]$ 的期望值，对 $10^9 + 7$ 取模。

在第一个测试用例中，$a = [1, 2]$，每个元素被插入 $S$ 的概率为 $\frac{1}{2}$，因为 $p_1 = p_2 = 5000$，$\frac{p_i}{10^4} = \frac{1}{2}$。因此，$S$ 有 $4$ 种可能：

• $S = \varnothing$，此时 $f(S) = 0$，$(f(S))^2 = 0$。
• $S = \{1\}$，此时 $f(S) = 1$，$(f(S))^2 = 1$。
• $S = \{2\}$，此时 $f(S) = 2$，$(f(S))^2 = 4$。
• $S = \{1,2\}$，此时 $f(S) = 1 \oplus 2 = 3$，$(f(S))^2 = 9$。

因此，答案为 $0 \cdot \frac{1}{4} + 1 \cdot \frac{1}{4} + 4\cdot \frac{1}{4} + 9 \cdot \frac{1}{4} = \frac{14}{4} = \frac{7}{2} \equiv 500\,000\,007 \pmod{10^9 + 7}$。

在第二个测试用例中，$a = [1, 1]$，$a_1$ 以概率 $0.1$ 被插入 $S$，$a_2$ 以概率 $0.2$ 被插入 $S$。$S$ 有 $3$ 种可能：

• $S = \varnothing$，此时 $f(S) = 0$，$(f(S))^2 = 0$，概率为 $(1-0.1) \cdot (1-0.2) = 0.72$。
• $S = \{1\}$，此时 $f(S) = 1$，$(f(S))^2 = 1$，概率为 $(1-0.1) \cdot 0.2 + 0.1 \cdot (1-0.2) = 0.26$。
• $S = \{1, 1\}$，此时 $f(S) = 0$，$(f(S))^2 = 0$，概率为 $0.1 \cdot 0.2 = 0.02$。

因此，答案为 $0 \cdot 0.72 + 1 \cdot 0.26 + 0 \cdot 0.02 = 0.26 = \frac{26}{100} \equiv 820\,000\,006 \pmod{10^9 + 7}$。

由 ChatGPT 4.1 翻译