HackerRank Combinatorics – Alien Flowers

Challenge: Alien Flowers

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464755270

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/alien-flowers/problem

Cerinta

Meera bought a house on Mars, and plans to decorate it with chains of alien flowers. Each flower is either red ($R$) or blue ($B$), and Meera knows how many occurrences of `RR`, `RB`, `BB`, and `BR` she wants to see in a chain. 	

The diagram below shows a flower chain of length $10$:

<img src="https://s3.amazonaws.com/hr-challenge-images/14591/1453204624-d20e72c6a1-ornament.jpg" title="ornament.jpg" />

In this example, `RR` occurs $2$ times (at positions $0$ and $4$), `RB` occurs $3$ times (at positions $1$, $5$, and $7$), `BB` occurs $1$ time (at position $2$), and `BR` occurs $3$ times (at positions $3$, $6$, and $8$).

Meera wants your help determining how many different chains with *positive length* can be made. Given $A, B, C$, and $D$, find the number of different chains having occurrences of `RR`, `RB`, `BB` and `BR` equal to inputs $A, B, C$, and $D$, respectively. As the answer can be very large, your printed output should be $answer \ \% \ (10^9+7)$.

Input Format

One line of space-separated, non-negative integers: $A$ (occurrences of `RR`), $B$ (occurrences of `RB`), $C$ (occurrences of `BB`), and $D$ (occurrences of `BR`), respectively.

Output Format

Find the number of chains having $A, B, C$, and $D$ occurrences of `RR`, `RB`, `BB`, and `BR`, respectively, and print the $answer \ \% \ (10^9+7)$.

Constraints

* For $20\%$ Points: $0 \leq A,B,C,D \leq 4$

* For $50\%$ Points: $0 \leq A,B,C,D \leq 10^2$

* For $100\%$ Points: $0 \leq A,B,C,D \leq 10^5$

Cod sursa

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

static const long long MOD = 1000000007LL;

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

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

    long long rr, rb, bb, br;
    cin >> rr >> rb >> bb >> br;

    if (llabs(rb - br) > 1) {
        cout << 0 << '\n';
        return 0;
    }

    long long maxK = max(rb, br);
    if (maxK >= MOD) {
        // Not expected under problem constraints.
        cout << 0 << '\n';
        return 0;
    }

    vector<long long> inv((size_t)maxK + 1, 1);
    for (long long i = 2; i <= maxK; ++i) {
        inv[(size_t)i] = MOD - (MOD / i) * inv[(size_t)(MOD % i)] % MOD;
    }

    auto comb = [&](long long n, long long k) -> long long {
        if (k < 0 || k > n) return 0;
        k = min(k, n - k);
        long long res = 1;
        for (long long i = 1; i <= k; ++i) {
            long long num = (n - k + i) % MOD;
            res = (res * num) % MOD;
            res = (res * inv[(size_t)i]) % MOD;
        }
        return res;
    };

    auto ways = [&](long long internal, long long runs) -> long long {
        if (runs == 0) return internal == 0 ? 1LL : 0LL;
        return comb(internal + runs - 1, runs - 1);
    };

    long long ans = 0;

    if (rb == br) {
        long long t = rb;
        // Start and end with R: R-runs=t+1, B-runs=t
        ans = (ans + ways(rr, t + 1) * ways(bb, t)) % MOD;
        // Start and end with B: R-runs=t, B-runs=t+1
        ans = (ans + ways(rr, t) * ways(bb, t + 1)) % MOD;
    } else if (rb == br + 1) {
        long long t = rb;
        // Start with R, end with B: R-runs=t, B-runs=t
        ans = (ans + ways(rr, t) * ways(bb, t)) % MOD;
    } else {
        long long t = br;
        // Start with B, end with R: R-runs=t, B-runs=t
        ans = (ans + ways(rr, t) * ways(bb, t)) % MOD;
    }

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