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

Cerință

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:

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

Output Format

Constraints

Cod sursă

#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;
}