Soluție HackerRank pentru Sherlock and Square, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Sherlock and Square
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Sherlock and Square
Subdomeniu: Algebra (algebra)
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464734347
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/sherlock-and-square/problem
Cerință
Watson gives a square of side length 1 to Sherlock. Now, after each second, each square of some arbitrary side L will break into four squares each of side L/2(as shown in the image below).
![img][123]
Now, Watson asks Sherlock: What will be the sum of length of solid lines after N seconds?
As the number can be large print result mod (10^9 + 7).
For example, after 0 seconds, the length is 4.
After 1 second, the length is 6.
Input Format
First line contains T, the number of testcases. Each testcase contains N in one line.
Output Format
For each testcase, print the required answer in a new line.
Constraints
1 ≤ T ≤ 10^5
0 ≤ N ≤ 10^9
Sample input
3
0
1
5
Sample output
4
6
66
[123]: http://i.imgur.com/yXME9kL.png
Cod sursă
//sherlock-and-square.cpp
//Sherlock and Square
//Weekly Challenges - Week 11
//Author: derekhh
#include<iostream>
using namespace std;
const int MOD = 1000000007;
int ModExp(int a, int b, int n)
{
long long c = 1, d = a;
while (b)
{
if (b & 1) c = (c*d) % n;
d = (d*d) % n;
b >>= 1;
}
return (int)c;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
cout << (ModExp(2, n + 1, MOD) + 2) % MOD << endl;
}
return 0;
}