Random OR Solution Codechef
Chef is playing a game, which he starts with a score of S=0. He also has an integer N.
In one move, Chef does the following:
- Uniformly randomly pick an integer X between 0 and 2N−1 (inclusive of both ends)
- Update his score as S→S∣X, where ∣∣ denotes the bitwise OR operation
For example, if Chef’s current score is S=6 and he picks X=10, his new score is 6∣10=14.
Chef stops when his score SS becomes equal to 2N−1. What is the expected number of moves Chef performs?
Output the answer modulo 109+7. That is, the answer can be expressed as a fraction P/Q, where gcd(Q,109+7)=1. Print P⋅Q−1(mod 109+7), where Q−1 denotes the modular multiplicative inverse of Q with respect to 109+7.
Input Format
- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains a single integer N.
Output Format
For each test case, output on a new line the expected number of moves Chef performs, modulo 109+7109+7.
Constraints
- 1≤T≤100
- 1≤N≤3⋅105
- Sum of N over all test cases do not exceed 3⋅105
Subtasks
Subtask 1 (30 points):
- 1≤N≤103
- Sum of N over all test cases doesn’t exceed 103
Subtask 2 (70 points):
- Original constraints
Sample Input 1
3
1
2
100Sample Output 1
2
666666674
328238032Explanation
Test case 1: In each move, Chef chooses either 0 or 1, each with a probability of 1/2. The game ends as soon as Chef chooses 1. Thus, the probability that the game takes exactly k moves is 2−k.
The required expected value is then ∑k=1∞k⋅2−k, which equals 2.
Test case 2: In each move, Chef chooses an integer in [0,3]. The answer is 8/3.
SOLUTION
Program: Random OR Solution in C++
#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9+7;
void calc_gcd(long long a, long long n, long long* x, long long* y){
if(a==0){
*x = 0;
*y = 1;
return;
}
long long X, Y;
calc_gcd(n%a, a, &X, &Y);
*x = Y - (n/a)*X;
*y = X;
return;
}
long long inverse(long long a, long long n){
long long x, y;
calc_gcd(a, n, &x, &y);
while(x<0) x+=n;
return x%n;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
long long t, n;
cin >> t;
while(t--){
cin >> n;
long long alt[] = {mod-1, 1};
long long comb = 1;
long long ans = 0;
long long pow2 = 1;
for(int i=1;i<=n;i++){
comb = (comb*(n-i+1))%mod;
comb = (comb*inverse(i, mod))%mod;
pow2 *= 2;
pow2 %= mod;
long long cur = (alt[i&1]*comb)%mod;
cur = (cur*pow2)%mod;
cur = (cur*inverse((pow2-1+mod)%mod, mod))%mod;
ans = (ans+cur)%mod;
}
cout << ans << "\n";
}
return 0;
}