PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: lavish_adm
Testers: utkarsh_adm, iceknight1093
DIFFICULTY:
1484
PREREQUISITES:
Basic modular arithmetic
PROBLEM:
You have to consider a sequence of numbers where the first element is X. And each element after it, is the sum of all the elements before it. And you need to output the sum of the first N elements of this sequence.
EXPLANATION:
Let us look at the first few elements of this sequence:
The first element is X.
The second element is the sum of everything which came before it, which is just X.
The third element is sum of first two, which is X+X = 2X.
The fourth element is sum of first three, which is X+X+2X = 4X.
The fifth element is sum of first four, which is X+X+2X+4X = 8X.
We see a pattern emerging. From the third element onwards, the elements seem to keep doubling. But it’s not obvious why that’s the case.
So now, instead, let’s look directly at the sum of the first i elements:
The sum of the first element is X.
The sum of the first two elements is X+X = 2X.
The sum of the first three elements is X+X + 2X= 4X.
The sum of the first four elements is X+X+2X+4X= 8X.
Here, we again see a very similar pattern, but now, starting from the second sum itself, the sums are double the previous sum.
And this is easy to see why - suppose the sum of the first 5 elements is some Y. Then the 6th element is Y, by definition. So then the sum of the first 6 elements is 2.
So generalizing this, we see that the sums are just X, 2X, 2^2X, 2^3X, 2^4X, 2^5X, \ldots. In particular, the sum of the first N elements is just 2^{N-1}X.
So given X and N, we just have to output (2^{N-1}X) \mod 1000000007. Since there are a lot of testcases, and the powers of 2 are independent of X, we can compute 2^{i} \mod 1000000007 for all values of i from 0 to 10^6, and store them in an array.
And we use the fact that (AB) \mod C = ( (A \mod C) * (B \mod C) ) \mod C to use the precomputed values of the modulos of the powers and get the answer for each testcase in constant time after the precomputation.
TIME COMPLEXITY:
Time complexity is O(N + T).
SOLUTION:
Tester's Solution
mod = 10**9 + 7
for _ in range(int(input())):
n, x = map(int, input().split())
print((pow(2, n-1, mod)*x)%mod)
Editorialist's Solution
#include <iostream>
using namespace std;
long long int testcases, Pow[1000001], n, x, MOD = 1000000007;
int main() {
cin>>testcases;
Pow[0]=1;
for(int i=1;i<=1000000;i++)
Pow[i] = (Pow[i-1] * 2) % MOD;
while(testcases--)
{
cin>>n>>x;
cout<<(x * Pow[n-1]) % MOD << "\n";
}
return 0;
}