HackerRank Combinatorics – Academy Surveillance – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Academy Surveillance

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464780731

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/surveillance/problem

Cerinta

The Academy is a school where each common area is laid out on an $m \times n$ grid and each cell in the grid is $1$ meter by $1$ meter. Danielle is their new head of security, and she wants to place a surveillance camera along every square meter of each common area. Because the school doesn't have enough money in their security budget to do this, she decides to further restrict camera placement according to the following rules:

- Each cell can contain *at most* $1$ camera.
- Every $3 \times 3$ subgrid of a common area *must* have exactly $2$ cameras.

Given the values of $m$ and $n$ for $c$ common areas, determine the number of ways Danielle can install cameras in each common area according to the rules above. Then, for each common area, print the number of ways she can install these cameras on a new line. As these values may be quite large, your answer must be modulo $10^9 + 7$.

Input Format

The first line contains an integer, $c$, denoting the number of common areas to install cameras in. 	 
Each line $i$ of the $c$ subsequent lines contains two space-separated integers describing the respective values of $m$ and $n$ for a common area's grid.

Output Format

For each common area, print an integer denoting the number of ways Danielle can install the cameras according to the given rules, modulo $10^9 + 7$, on a new line.

Constraints

For $\text{20%}$ of the maximum score:   

+ $1 \le c \le 10$  
+ $3 \le m, n \le 15$  

For $\text{50%}$ of the maximum score:   

+ $1 \le c \le 100$  
+ $3 \le m, n \le 50$  

For $\text{100%}$ of the maximum score:   

+ $1 \le c \le 10^5$  
+ $3 \le m, n \le 1000$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (__int128)r * a % MOD;
        a = (__int128)a * a % MOD;
        e >>= 1;
    }
    return r;
}

// count of indices 0..len-1 with idx%3=r
long long cnt_mod3(long long len, int r) {
    // (len + (2-r)) / 3
    return (len + (2 - r)) / 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long n, m;
        cin >> n >> m;

        // Daca n<3 sau m<3 nu exista ferestre 3x3 => nicio restrictie
        if (n < 3 || m < 3) {
            cout << modpow(2, n * m) << "\n";
            continue;
        }

        long long r[3] = {cnt_mod3(m,0), cnt_mod3(m,1), cnt_mod3(m,2)};

        long long lenRow[3] = {cnt_mod3(n,0), cnt_mod3(n,1), cnt_mod3(n,2)};
        long long s[3] = {max(0LL, lenRow[0]-1), max(0LL, lenRow[1]-1), max(0LL, lenRow[2]-1)}; // sum = n-3

        auto p2 = [&](long long e){ return modpow(2, e); };
        auto p3 = [&](long long e){ return modpow(3, e); };

        long long ans = 0;

        // termenii de baza (cazul n=3)
        ans = (ans + p3(r[0]+r[1])) % MOD;
        ans = (ans + p3(r[0]+r[2])) % MOD;
        ans = (ans + p3(r[1]+r[2])) % MOD;
        ans = (ans + p3(r[0])) % MOD;
        ans = (ans + p3(r[1])) % MOD;
        ans = (ans + p3(r[2])) % MOD;

        // corectii pentru n>3
        long long t1 = 0;
        t1 = (t1 + (p3(s[0]+s[1]) - 1 + MOD) % MOD) % MOD;
        t1 = (t1 + (p3(s[0]+s[2]) - 1 + MOD) % MOD) % MOD;
        t1 = (t1 + (p3(s[1]+s[2]) - 1 + MOD) % MOD) % MOD;
        ans = (ans + 9LL * t1) % MOD;

        long long a1 = (p2(r[0]) + p2(r[1]) + p2(r[2]) - 5) % MOD;
        if (a1 < 0) a1 += MOD;

        long long b1 = 0;
        b1 = (b1 + (p3(s[0]) - 1 + MOD) % MOD) % MOD;
        b1 = (b1 + (p3(s[1]) - 1 + MOD) % MOD) % MOD;
        b1 = (b1 + (p3(s[2]) - 1 + MOD) % MOD) % MOD;

        ans = (ans + 3LL * a1 % MOD * b1) % MOD;

        long long a2 = 0;
        for (int i=0;i<3;i++){
            long long v = (p3(r[i]) - p2(r[i]) - 1) % MOD;
            if (v < 0) v += MOD;
            a2 = (a2 + v) % MOD;
        }

        long long b2 = 0;
        for (int i=0;i<3;i++){
            long long v = (p2(s[i]) - 1) % MOD;
            if (v < 0) v += MOD;
            b2 = (b2 + v) % MOD;
        }

        ans = (ans + 2LL * a2 % MOD * b2) % MOD;

        cout << ans % MOD << "\n";
    }
    return 0;
}

HackerRank Combinatorics – Academy Surveillance