Дан массив, состоящий из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$. Также дан массив $$$p_1, p_2, \ldots, p_n$$$.
Через $$$S$$$ обозначим случайное мультимножество (т. е. оно может содержать равные элементы), которое строится следующим образом:
Пусть $$$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$$$.
421 25000 500021 11000 20006343 624 675 451 902 8206536 5326 7648 2165 9430 54281110000
500000007 820000006 280120536 1
В первом наборе входных данных $$$a = [1, 2]$$$, и каждый элемент добавляется в $$$S$$$ с вероятностью $$$\frac{1}{2}$$$, поскольку $$$p_1 = p_2 = 5000$$$ и $$$\frac{p_i}{10^4} = \frac{1}{2}$$$. Поэтому есть всего $$$4$$$ возможных исхода для $$$S$$$, каждый из которых получается с вероятностью $$$\frac{1}{4}$$$:
Значит, ответ равен $$$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$$$ добавляется в $$$S$$$ с вероятностью $$$0.1$$$, а $$$a_2$$$ добавляется в $$$S$$$ с вероятностью $$$0.2$$$. Есть всего $$$3$$$ исхода для $$$S$$$:
Значит, ответ равен $$$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}$$$.
Название |
---|