#PROBLEM LINK:
contest
#PREREQUISITES:
Progression, Modular-arithematic
#Problem:
The first row contains number from 1 to N. Then the next line will contain N-1 numbers, In the second row, the first number will be the summation of the first two numbers of the previous row, the second number will be the summation of the second two numbers of the previous row and so on. Row 3 will have N-2 numbers with same procedures. Same procedure follows for row 4, row 5, … , row N. On the last row, there will be only a single number. Calculate the number in the nth row.
#Explanation:
For a given value of n we can derive a formula using basic progression sequence.
The formula for any given value of n is [(n+1)*2^{n-2}]
and for n = 1 and 2 answer would be 1 and 3 respectively .We have to apply modular arithematic to calculate the value as it may lead to overflow in case of some programming language.
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
LL pow_mod(int n)
{
LL a = 1 , p = 2;
while(n)
{
if(n&1)
a = (a*p)%MOD;
p = (p*p)%MOD;
n>>=1;
}
return a;
}
int main()
{
int t , j = 1;
cin>>t;
while(t--)
{
LL n;
cin>>n;
if(n==1)
{
cout<<"Case "<<j<<": "<<1<<endl;
j++;
continue;
}
if(n == 2)
{
cout<<"Case "<<j<<": "<<3<<endl;
j++;
continue;
}
cout<<"Case "<<j<<": "<<((n+1) * (pow_mod(n-2)))%MOD<<endl;
j++;
}
return 0;
}