USER
optimum cpp solution for : Expected Power
time limit per test4 seconds
memory limit per test256 megabytes
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:
Initially, S
is empty.
For each i
from 1
to n
, insert ai
into S
with probability pi104
. 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 109+7
.
Formally, let M=109+7
. It can be shown that the answer can be expressed as an irreducible fraction pq
, where p
and q
are integers and q≢0(modM)
. Output the integer equal to p⋅q−1modM
. In other words, output such an integer x
that 0≤x<M
and x⋅q≡p(modM)
.
Input
Each test contains multiple test cases. The first line contains the number of test cases t
(1≤t≤104
). The description of the test cases follows.
The first line of each test case contains a single integer n
(1≤n≤2⋅105
).
The second line of each test case contains n
integers a1,a2,…,an
(1≤ai≤1023
).
The third line of each test case contains n
integers p1,p2,…,pn
(1≤pi≤104
).
It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105
.
Output
For each test case, output the expected value of (f(S))2
, modulo 109+7
.
Example
InputCopy
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
OutputCopy
500000007
820000006
280120536
1
Note
In the first test case, a=[1,2]
and each element is inserted into S
with probability 12
, since p1=p2=5000
and pi104=12
. Thus, there are 4
outcomes for S
, each happening with the same probability of 14
:
S=∅
. 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⊕2=3
, (f(S))2=9
.
Hence, the answer is 0⋅14+1⋅14+4⋅14+9⋅14=144=72≡500000007(mod109+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 0⋅0.72+1⋅0.26+0⋅0.02=0.26=26100≡820000006(mod109+7)
.ASSISTANT
To solve the problem, we need to compute the expected value of the square of the bitwise XOR of a random subset of an array. The approach involves breaking down the problem bit by bit and leveraging properties of probabilities and modular arithmetic.
### Step-by-Step Explanation
1. **Understanding XOR and Expectation:**
- The XOR of a subset can be expressed as the sum of its bits. If we denote each bit position `k`, the XOR can be written as `f(S) = Σ (X_k * 2^k)`, where `X_k` is the parity (0 or 1) of the count of selected elements that have the `k-th` bit set.
- The expected value of `(f(S))^2` can be expanded as:
\[
E[(f(S))^2] = \sum_{k} 4^k E[X_k] + \sum_{k \neq l} 2^{k+l} E[X_k X_l]
\]
where `E[X_k]` is the expectation of the k-th bit being set, and `E[X_k X_l]` is the expectation that both the `k-th` and `l-th` bits are set.
2. **Calculating Probabilities:**
- For each bit `k`, compute the probability `P(X_k = 1)` that the k-th bit is set in the XOR of the subset. This is given by:
\[
P(X_k = 1) = \frac{1 - \prod_{i \in A_k} (1 - 2q_i)}{2}
\]
where `A_k` is the set of indices where the k-th bit is set in the array, and `q_i` is the probability of including the i-th element divided by 10,000.
- For each pair of bits `(k, l)`, compute the joint probability `P(X_k = 1 AND X_l = 1)` that both the k-th and l-th bits are set in the XOR. This involves categorizing elements into three groups based on their bitmask and calculating the probabilities accordingly.
3. **Implementation Details:**
- Precompute powers of 2 up to 20 for efficiency.
- Use modular arithmetic to handle large numbers, particularly with a modulus of \(10^9 + 7\).
- Group elements by their bitmask and compute products for different groups to efficiently calculate the necessary probabilities.
- Combine these probabilities to compute the final expected value using the formula mentioned above.
4. **Handling Multiple Test Cases Efficiently:**
- Given the constraints where the sum of `n` across all test cases is up to \(2 \times 10^5\), the solution is optimized to handle computations efficiently within the given limits.
### Final Implementation
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1000000007;
// Function to compute x^power mod M
ll power_mod(ll x, ll power, ll mod) {
ll res = 1;
x %= mod;
while(power > 0){
if(power & 1) res = res * x % mod;
x = x * x % mod;
power >>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
// Precompute inv10000 and inv2
ll inv10000 = power_mod(10000, M-2, M);
ll inv2 = power_mod(2, M-2, M); // 500000004 for M=1e9+7
// Precompute powers of 2 up to 20
ll pow2[21];
pow2[0] =1;
for(int i=1;i<=20;i++) pow2[i] = pow2[i-1] * 2 % M;
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
for(auto &x: a) cin >> x;
vector<int> p(n);
for(auto &x: p) cin >> x;
// Compute q_i = p_i * inv10000 % M
vector<ll> q(n);
for(int i=0;i<n;i++) q[i] = ( (ll)p[i] * inv10000 ) % M;
// Compute bitmask for each element
vector<int> m_i(n, 0);
for(int i=0;i<n;i++){
int num = a[i];
for(int b=0;b<10;b++) {
if(num & (1<<b)) m_i[i] |= (1<<b);
}
}
// Compute product_m[m} = product (1 - 2*q_i) for all elements with bitmask m
// There are 1024 possible m
vector<ll> product_m(1024, 1);
for(int i=0;i<n;i++){
int m = m_i[i];
ll term = (1 - 2 * q[i] % M + M) % M;
product_m[m] = product_m[m] * term % M;
}
// Compute E[Xk} for each bit k
vector<ll> E_Xk(10, 0);
for(int k=0;k<10;k++){
ll product_k =1;
for(int m=0;m<1024;m++){
if(m & (1<<k)){
product_k = product_k * product_m[m] % M;
}
}
E_Xk[k] = ( (1 - product_k + M) % M ) * power_mod(2, M-2, M) % M;
}
// Compute E[Xk Xl} for all k < l
// Store in a 10x10 matrix, but only k < l
// Initialize a 10x10 matrix with 0
vector<vector<ll>> E_Xk_Xl(10, vector<ll>(10, 0));
for(int k=0;k<10;k++){
for(int l=k+1;l<10;l++){
ll product_a =1, product_b=1, product_d=1;
for(int m=0;m<1024;m++){
if( (m & (1<<k)) && !(m & (1<<l)) ){
product_a = product_a * product_m[m] % M;
}
if( (m & (1<<l)) && !(m & (1<<k)) ){
product_b = product_b * product_m[m] % M;
}
if( (m & (1<<k)) && (m & (1<<l)) ){
product_d = product_d * product_m[m] % M;
}
}
ll P_a_odd = ((1 - product_a + M) % M ) * inv2 % M;
ll P_b_odd = ((1 - product_b + M) % M ) * inv2 % M;
ll P_d_odd = ((1 - product_d + M) % M ) * inv2 % M;
ll term1 = ( ( (1 - P_a_odd + M) % M ) * ( (1 - P_b_odd + M) % M ) ) % M;
term1 = term1 * P_d_odd % M;
ll term2 = (P_a_odd * P_b_odd) % M;
term2 = term2 * ((1 - P_d_odd + M) % M) % M;
ll E = (term1 + term2) % M;
E_Xk_Xl[k][l] = E;
}
}
// Now compute the final expected value
ll result =0;
for(int k=0;k<10;k++){
ll term = power_mod(2, 2*k, M) * E_Xk[k] % M;
result = (result + term) % M;
}
for(int k=0;k<10;k++){
for(int l=k+1;l<10;l++){
ll term = power_mod(2, k + l, M) * E_Xk_Xl[k][l] % M;
term = (term * 2) % M;
result = (result + term) % M;
}
}
cout << result << "\n";
}
}
```