[Solution] 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 2N12N−1 (inclusive of both ends)
  • Update his score as SSXS→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 610=146∣10=14.

Chef stops when his score SS becomes equal to 2N12N−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 PQ1(mod 109+7)P⋅Q−1(mod 109+7), where Q1Q−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

  • 1T1001≤T≤100
  • 1N31051≤N≤3⋅105
  • Sum of NN over all test cases do not exceed 31053⋅105

Subtasks

Subtask 1 (30 points):

  • 1N1031≤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 2k2−k.

The required expected value is then k=1k2k∑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.

Leave a Comment