The Magical Stone CodeChef Solution | CodeChef Problem Solution 2022

The Magical Stone CodeChef Solution | CodeChef Problem Solution 2022

Initially, there is a magical stone of mass 2N$2^N$ lying at the origin of the number line. For the next N$N$ 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>1$M>1$ lying at coordinate X$X$, then it decomposes into two magical stones, each of mass M2$\frac{M}{2}$ lying at the coordinates X−1$X-1$ and X+1$X+1$ respectively. The original stone of mass M$M$ 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 X$X$.

Solution Click Below:-  CLICK HERE

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)$({10}^9+7)$.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.

Four Arrays CodeChef Solution | CodeChef Problem Solution 2022

In The Green Zone CodeChef Solution | CodeChef Problem Solution 2022

Football Cup CodeChef Solution | CodeChef Problem Solution 2022

Miami GP CodeChef Solution | CodeChef Problem Solution 2022

Sugarcane Juice Business CodeChef Solution 

The Attack of Queen CodeChef Solution | CodeChef Problem Solution 2022

Pushpa CodeChef Solution | CodeChef Problem Solution 2022

Mystical Numbers CodeChef Solution | CodeChef Problem Solution 2022

Alternating Diameter CodeChef Solution | CodeChef Problem Solution 2022

The Magical Stone CodeChef Solution | CodeChef Problem Solution 2022

• The first and only line of each test case contains three integers N$N$, L$L$ and R$R$, as described in the problem statement.

Output Format

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

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤106$1\le N\le {10}^6$
• −N≤L≤R≤N$-N\le L\le R\le N$
• Sum of (R−L+1)$(R-L+1)$ over all the test cases doesn't exceed 105${10}^5$.

Sample Input 1 

3
2 -2 2
2 0 2
150000 48 48

Sample Output 1 

1 0 2 0 1
2 0 1
122830846

Explanation

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

t=0$t=0$: {0,0,1,0,0}$\{0,0,1,0,0\}$

t=1$t=1$: {0,1,0,1,0}$\{0,1,0,1,0\}$

t=2$t=2$: {1,0,2,0,1}$\{1,0,2,0,1\}$

We have to output the number of stones at x=−2$x=-2$ to x=2$x=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=0$x=0$ to x=2$x=2$, which is {2,0,1}$\{2,0,1\}$.

Join Now for Solution:-