PROBLEM LINK:
Author: Ishika Chowdhury
Testers: Hritesh Maurya
Editorialist: Ishika Chowdhury
DIFFICULTY:
Easy
PROBLEM:
Ash is about to take on his long-time rival, Gary Oak, in the next battle of the Johto League Silver Conference and he’s determined to do everything he can to win.
The pokemons are given N cards. Their task is to find the total number of ways such that 2 cards always face the front and 2 cards always face backwards.
Whoever cracks it first, will be close to victory. Help Ash to win this task.
EXPLANATION:
Since 2 card always face the front and 2 cars always face backwards, for N < 4, so the total number of ways will be 0.
For N >= 4,
Total number of ways will be 2^N -2N - 2
Time Complexity:
The time complexity is O( T * ( log N )) , T : number of test cases.
Solution:
Setter's Solution
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main() {
ll t;
cin >> t;
assert(1 <= t && t <= 1e5);
ll mod = 1e9 + 7;
while(t--) {
ll n;
cin >> n;
assert(1 <= n && n <= 1e18);
if(n <= 3) {
cout << "0\n";
continue;
}
ll cp = n;
ll ans = 1 % mod;
ll a = 2 % mod;
while(n != 0) {
if(n & 1)
ans = ((ans % mod) * (a % mod)) % mod;
a = ((a % mod) * (a % mod)) % mod;
n >>= 1;
}
ll x = ((2 % mod) * (cp % mod)) % mod;
ll y = ((x % mod) + (2 % mod)) % mod;
ll sol = ((ans % mod) - (y % mod) + mod) % mod;
cout << sol << "\n";
}
}