Soluție HackerRank pentru Manasa and Combinatorics, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…

  • Problemă: Manasa and Combinatorics
  • Domeniu: Combinatorics
  • Limbaj: C++14

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

Cerință

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

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.

In second case, "BBAABB", "BABABB" , "BBABAB" and "BABBAB" are valid strings.

Cod sursă

#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;
}
HackerRank Combinatorics – Manasa and Combinatorics