HackerRank Combinatorics – Tower 3-coloring

Challenge: Tower 3-coloring

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464727825

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/tower-3-coloring/problem

Cerinta

For a given integer $n$, there is a tower built from $3^n$ blocks stacked vertically. Each of these blocks can be colored in $3$ different colors: red, green or blue. How many different colorings of the tower can be created? Two colorings are considered different if and only if there exists at least one block with different colors in the colorings. Since the result can be a huge number, apply a modulo $10^9 + 7$ on the result.

Input Format

The first line contains a single integer $n$.

Output Format

In a single line print a single integer denoting the number of different colorings of tower of the height $3^n$ calculated modulo $10^9+7$.

Constraints

+ $1 \leq n \leq 10^9$

Cod sursa

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;
ll power(ll x, ll y, ll p)
{
    ll res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}


// Complete the towerColoring function below.
ll towerColoring(ull n) {
        ll p = 1e9 + 7;

    ll yy = (power(3, n, p - 1)) % (p-1);
  ll res = power(3, yy, p) % p;
    return res;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    ll n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    ll result = towerColoring(n);

    fout << result << "\n";

    fout.close();

    return 0;
}