The Magical Stone solution codechef

The Magical Stone solution codechef

 

Initially, there is a magical stone of mass 2N2N lying at the origin of the number line. For the next NN seconds, the following event happens:

  • Let us define the decomposition of a magical stone as follows: If there is a magical stone of mass M>1M>1 lying at coordinate XX, then it decomposes into two magical stones, each of mass M2M2 lying at the coordinates X1X−1 and X+1X+1 respectively. The original stone of mass MM gets destroyed in the process.
  • Each second, all the magical stones undergo decomposition simultaneously.

Note that there can be more than one stone at any coordinate XX.

Given a range [L,R][L,R], find out the number of stones present at each of the coordinates in the range [L,R][L,R]. As the number of stones can be very large, output them modulo (109+7)(109+7).

 The Magical Stone solution codechef

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first and only line of each test case contains three integers NNLL and RR, as described in the problem statement.

Output Format

For each testcase, output in a single line a total of (RL+1)(R−L+1) space-separated integers. The ithith integer will denote the number of stones present at X=(L+i1)X=(L+i−1) coordinate. As the number of stones can be very large, output them modulo (109+7)(109+7).

Constraints

  • 1T1001≤T≤100
  • 1N1061≤N≤106
  • NLRN−N≤L≤R≤N
  • Sum of (RL+1)(R−L+1) over all the test cases doesn’t exceed 105105.

Sample Input 1 

3
2 -2 2
2 0 2
150000 48 48
[Answer] The Magical Stone solution codechef

 

1 0 2 0 1
2 0 1
122830846

The Magical Stone solution codechef

Test case 1: Let us look at the number of stones for x=2x=−2 to x=2x=2 as the time progresses:

t=0t=0{0,0,1,0,0}{0,0,1,0,0}

t=1t=1{0,1,0,1,0}{0,1,0,1,0}

t=2t=2{1,0,2,0,1}{1,0,2,0,1}

We have to output the number of stones at x=2x=−2 to x=2x=2, which is {1,0,2,0,1}{1,0,2,0,1}.

Test case 2: Similar to first test case, We have to output the number of stones at x=0x=0 to x=2x=2, which is {2,0,1}{2,0,1}.

 Solution

Click here

Leave a Comment

Your email address will not be published.