Random OR Solution Codechef

Random OR Solution Codechef

Chef is playing a game, which he starts with a score of S=0S=0. He also has an integer NN.

In one move, Chef does the following:

  • Uniformly randomly pick an integer XX between 00 and 2N−12N−1 (inclusive of both ends)
  • Update his score as S→S∣XS→S∣X, where ∣∣ denotes the bitwise OR operation

For example, if Chef’s current score is S=6S=6 and he picks X=10X=10, his new score is 6∣10=146∣10=14.

Chef stops when his score SS becomes equal to 2N−12N−1. What is the expected number of moves Chef performs?

Output the answer modulo 109+7109+7. That is, the answer can be expressed as a fraction P/QP/Q, where gcd(Q,109+7)=1gcd(Q,109+7)=1. Print P⋅Q−1(mod 109+7)P⋅Q−1(mod 109+7), where Q−1Q−1 denotes the modular multiplicative inverse of QQ with respect to 109+7109+7.

Input Format

  • The first line of input contains an integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains a single integer NN.

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≤1001≤T≤100
  • 1≤N≤3⋅1051≤N≤3⋅105
  • Sum of NN over all test cases do not exceed 3⋅1053⋅105

Subtasks

Subtask 1 (30 points):

  • 1≤N≤1031≤N≤103
  • Sum of NN over all test cases doesn’t exceed 103103

Subtask 2 (70 points):

  • Original constraints

Sample Input 1 

3
1
2
100

Sample Output 1 

2
666666674
328238032

Explanation

Test case 11: In each move, Chef chooses either 00 or 11, each with a probability of 1/21/2. The game ends as soon as Chef chooses 11. Thus, the probability that the game takes exactly kk moves is 2−k2−k.

The required expected value is then ∑k=1∞k⋅2−k∑k=1∞k⋅2−k, which equals 22.

Test case 22: In each move, Chef chooses an integer in [0,3][0,3]. The answer is 8/38/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;
}

February Long Challenge 2022 Solution

January Long Challenge 2022 Solution

Leave a Comment

12 + eighteen =