HackerRank Combinatorics – Manasa and Combinatorics

Challenge: Manasa and Combinatorics

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464759434

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/manasa-and-combinatorics/problem

Cerinta

Manasa has a string having **N** number of A's and **2\*N** number of B's. She wants to arrange these characters in such a way that in each prefix and in each suffix of the string the number of **B**'s is greater than or equal to the number of **A**'s. Given the value of N, she wants to find the number of ways to do so.

**Input Format**  
The first line contains an integer T i.e. number of test cases.  
Next T lines will contain an integer N.  

**Output Format**  
A single line containing number of ways MOD 99991.

**Constraints**  
1 <= T <= 25<br> 
1 <= N <= 10<sup>12</sup>  

**Sample Input #00**  

	2
    1
    2

    
**Sample Output #00**  

    1
    4

**Explanation**  

In first case, "BAB" is only valid string.<br>
In second case, "BBAABB", "BABABB" , "BBABAB" and "BABBAB" are valid strings.

Cod sursa

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

static const int MOD = 99991;

long long modPow(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);

    vector<int> fact(MOD), ifact(MOD);
    fact[0] = 1;
    for (int i = 1; i < MOD; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;
    ifact[MOD - 1] = modPow(fact[MOD - 1], MOD - 2);
    for (int i = MOD - 1; i >= 1; --i) ifact[i - 1] = (long long)ifact[i] * i % MOD;

    auto Csmall = [&](int n, int r) -> int {
        if (r < 0 || r > n) return 0;
        return (long long)fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    };

    function<int(long long, long long)> Lucas = [&](long long n, long long r) -> int {
        if (r < 0 || r > n) return 0;
        long long res = 1;
        while (n > 0 || r > 0) {
            int ni = (int)(n % MOD);
            int ri = (int)(r % MOD);
            if (ri > ni) return 0;
            res = res * Csmall(ni, ri) % MOD;
            n /= MOD;
            r /= MOD;
        }
        return (int)res;
    };

    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;

        long long n3 = 3LL * N;

        int a = Lucas(n3, N);      // C(3N, N)
        int b = Lucas(n3, N - 1);  // C(3N, N-1)
        int c = Lucas(n3, N - 2);  // C(3N, N-2)

        int ans = (a + c - 2LL * b) % MOD;
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }

    return 0;
}