1/23/25, 7:29 PM Problem - 2020E - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 976 (Div. 2) and
E. Expected Power Divide By Zero 9.0
Finished
time limit per test: 4 seconds
memory limit per test: 256 megabytes Practice
You are given an array of n integers a1 , a2 , … , an . You are also given an array
p1 , p2 , … , pn .
Let S denote the random multiset (i. e., it may contain equal elements) constructed as follows: → Virtual participation
Virtual contest is a way to take part in past contest,
Initially, S is empty. as close as possible to participation on time. It is
pi
supported only ICPC mode for virtual contests. If
For each i from 1 to n , insert ai into S with probability 4
. Note that each element is you've seen these problems, a virtual contest is not
10
for you - solve these problems in the archive. If you
inserted independently. just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
Denote f (S ) as the bitwise XOR of all elements of S . Please calculate the expected value of the archive. Never use someone else's code, read
the tutorials or communicate with other person
(f (S ))
2
. Output the answer modulo 10
9
+ 7 . during a virtual contest.
9 Start virtual contest
Formally, let M = 10 + 7 . It can be shown that the answer can be expressed as an irreducible
p
fraction q
, where p and q are integers and q ≢ 0 (mod M) . Output the integer equal to
p ⋅ q
−1
mod M
x ⋅ q ≡ p (mod
. In other words, output such an integer x that 0
M).
≤ x < M and → Clone Contest to Mashup
Input → Submit?
Each test contains multiple test cases. The first line contains the number of test cases t (
4
1 ≤ t ≤ 10 ). The description of the test cases follows. Language: GNU G++20 13.2 (64 bit, winlibs)
The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10
5
). Choose
Choose File No file chosen
file:
The second line of each test case contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 1023 ). Submit
4
The third line of each test case contains n integers p 1 , p 2 , … , p n (1 ≤ p i ≤ 10 ).
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
5
→ Contest materials
Output Announcement (en)
For each test case, output the expected value of (f (S ))2 , modulo 109 + 7 . Tutorial #1 (en)
Example Video Tutorial (en)
input Copy
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
output Copy
500000007
820000006
280120536
1
Note
In the first test case, a = [1, 2] and each element is inserted into S with probability 1
, since
2
pi
p 1 = p 2 = 5000 and 4
=
1
. Thus, there are 4 outcomes for S , each happening with the
10 2
same probability of 1
:
4
S = ∅ . In this case, f (S ) ,
= 0 (f (S ))
2
= 0 .
[Link] 1/2
1/23/25, 7:29 PM Problem - 2020E - Codeforces
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 ⊕ 2 = 3 (f (S )) , 2
= 9 .
Hence, the answer is
1 1 1 1 14 7 9
0 ⋅
4
+ 1 ⋅
4
+ 4 ⋅
4
+ 9 ⋅
4
=
4
=
2
≡ 500 000 007 (mod 10 + 7) .
In the second test case, a = [1, 1] , a1 is inserted into S with probability 0.1, while a2 is inserted
into S with probability 0.2. There are 3 outcomes for S :
S = ∅ . In this case, f (S ) ,
= 0 (f (S ))
2
= 0 . This happens with probability
(1 − 0.1) ⋅ (1 − 0.2) = 0.72 .
S = {1} . In this case, f (S ) ,
= 1 (f (S ))
2
= 1 . This happens with probability
(1 − 0.1) ⋅ 0.2 + 0.1 ⋅ (1 − 0.2) = 0.26 .
S = {1, 1} . In this case, f (S ) ,
= 0 (f (S ))
2
= 0 . This happens with probability
0.1 ⋅ 0.2 = 0.02 .
Hence, the answer is
26 9
0 ⋅ 0.72 + 1 ⋅ 0.26 + 0 ⋅ 0.02 = 0.26 =
100
≡ 820 000 006 (mod 10 + 7) .
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/23/2025 11:34:14UTC+5 (i2).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
[Link] 2/2