Expected Power
Contest: Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
Difficulty rating: 2000
Tags: bitmasks, dp, math, probabilities

You are given an array of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. You are also given an array $$$p_1, p_2, \ldots, p_n$$$.

Let $$$S$$$ denote the random multiset (i. e., it may contain equal elements) constructed as follows:

- Initially, $$$S$$$ is empty.
- For each $$$i$$$ from $$$1$$$ to $$$n$$$, insert $$$a_i$$$ into $$$S$$$ with probability $$$\frac{p_i}{10^4}$$$. Note that each element is inserted independently.

Denote $$$f(S)$$$ as the bitwise XOR of all elements of $$$S$$$. Please calculate the expected value of $$$(f(S))^2$$$. Output the answer modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1023$$$).

The third line of each test case contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le 10^4$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the expected value of $$$(f(S))^2$$$, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$a = [1, 2]$$$ and each element is inserted into $$$S$$$ with probability $$$\frac{1}{2}$$$, since $$$p_1 = p_2 = 5000$$$ and $$$\frac{p_i}{10^4} = \frac{1}{2}$$$. Thus, there are $$$4$$$ outcomes for $$$S$$$, each happening with the same probability of $$$\frac{1}{4}$$$:

- $$$S = \varnothing$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$.
- $$$S = \{1\}$$$. In this case, $$$f(S) = 1$$$, $$$(f(S))^2 = 1$$$.
- $$$S = \{2\}$$$. In this case, $$$f(S) = 2$$$, $$$(f(S))^2 = 4$$$.
- $$$S = \{1,2\}$$$. In this case, $$$f(S) = 1 \oplus 2 = 3$$$, $$$(f(S))^2 = 9$$$.

Hence, the answer is $$$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}$$$.

In the second test case, $$$a = [1, 1]$$$, $$$a_1$$$ is inserted into $$$S$$$ with probability $$$0.1$$$, while $$$a_2$$$ is inserted into $$$S$$$ with probability $$$0.2$$$. There are $$$3$$$ outcomes for $$$S$$$:

- $$$S = \varnothing$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. This happens with probability $$$(1-0.1) \cdot (1-0.2) = 0.72$$$.
- $$$S = \{1\}$$$. In this case, $$$f(S) = 1$$$, $$$(f(S))^2 = 1$$$. This happens with probability $$$(1-0.1) \cdot 0.2 + 0.1 \cdot (1-0.2) = 0.26$$$.
- $$$S = \{1, 1\}$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. This happens with probability $$$0.1 \cdot 0.2 = 0.02$$$.

Hence, the answer is $$$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}$$$.

Example input:
4
2
1 2
5000 5000
2
1 1
1000 2000
6
343 624 675 451 902 820
6536 5326 7648 2165 9430 5428
1
1
10000

Example output:
500000007
820000006
280120536
1

Editorial:
Let the binary representation of the $$$Power$$$ be $$$b_{20}b_{19}...b_{0}$$$. Now $$$Power^2$$$ is $$$\sum_{i=0}^{20} \sum_{j=0}^{20} b_i b_j * 2^{i+j}$$$. Now if we compute the expected value of $$$b_ib_j$$$ for every pair $$$(i,j)$$$, then we are done.
We can achieve this by dynamic programming. For each pair $$$i,j$$$, there are only 4 possible values of $$$b_i,b_j$$$. For every possible value, we can maintain the probability of reaching it, and we are done.
The complexity of the solution is $$$O(n.log(max(a_i))^2)$$$.