Random OR Solution Codechef

Table of Contents

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
100

Sample Output 1

2
666666674
328238032

Explanation

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;
}

February Long Challenge 2022 Solution

Leave a Comment

five × 5 =