← 返回题目列表

Codeforces · 2020/E

E. 预期功率

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 整数数组 $$$a_1,a_2,\ldots,a_n$$$。您还会获得一个数组 $$$p_1, p_2, \ldots, p_n$$$。

让 $$$S$$$ 表示随机多重集(即,它可能包含相等的元素),构造如下:

- 最初,$$$S$$$ 是空的。
- 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,将 $$$a_i$$$ 插入到 $$$S$$$ 中,概率为 $$$\frac{p_i}{10^4}$$$。请注意,每个元素都是独立插入的。

将 $$$f(S)$$$ 表示为 $$$S$$$ 的所有元素的按位异或。请计算$$$(f(S))^2$$$的期望值。输出对 $$$10^9 + 7$$$ 取模的答案。

正式地,让 $$$M = 10^9 + 7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 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 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$(f(S))^2$$$ 的期望值,模 $$$10^9 + 7$$$。

示例

输入 #1

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

输出 #1

500000007
820000006
280120536
1

注意

在第一个测试用例中,$$$a = [1, 2]$$$,并且每个元素以 $$$\frac{1}{2}$$$ 的概率插入到 $$$S$$$ 中,因为 $$$p_1 = p_2 = 5000$$$ 且 $$$\frac{p_i}{10^4} = \frac{1}{2}$$$。因此,$$$S$$$ 有 $$$4$$$ 个结果,每个结果的发生概率相同 $$$\frac{1}{4}$$$:

- $$$S = \var没有$$$。在这种情况下,$$$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 = \var没有$$$。在这种情况下,$$$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}$$$。