HackerRank Geometry – Polygons

Challenge: Polygons

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464761891

Limbaj: cpp14

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

Cerinta

Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.

**Input:**  
The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.

**Output:**  
Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.

**Constraints:**  
1 <= T <= 10000  
4 <= N <= 10^9  
1 <= K <= N 

**Sample Input:**  
3  
4 1  
5 2  
5 3

**Sample Output:**  
2  
5  
0

**Explanation:**

For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).  
For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

Cod sursa

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

static const int MOD = 1000003;

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

long long modinv(long long a) {
    a %= MOD;
    if (a < 0) a += MOD;
    return modpow(a, MOD - 2);
}

vector<int> fact;

long long vp_fact(long long n) {
    long long e = 0;
    while (n > 0) {
        n /= MOD;
        e += n;
    }
    return e;
}

long long fact_no_p(long long n) {
    if (n == 0) return 1;
    long long q = n / MOD;
    long long r = n % MOD;

    long long res = fact_no_p(q);
    if (q & 1LL) res = res * (MOD - 1) % MOD; // Wilson block sign
    res = res * fact[(int)r] % MOD;
    return res;
}

struct BinomPE {
    long long unit; // binomial with p-factors removed, modulo p
    long long exp;  // exponent of p in binomial
};

BinomPE binom_pe(long long n, long long k) {
    if (k < 0 || k > n) return {0, (long long)4e18};
    long long e = vp_fact(n) - vp_fact(k) - vp_fact(n - k);

    long long a = fact_no_p(n);
    long long b = fact_no_p(k);
    long long c = fact_no_p(n - k);

    long long u = a;
    u = u * modinv(b) % MOD;
    u = u * modinv(c) % MOD;
    return {u, e};
}

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

    fact.assign(MOD, 1);
    for (int i = 1; i < MOD; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;

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

        if (k < 0 || k > n - 3) {
            cout << 0 << '\n';
            continue;
        }

        // D(n,k) = C(n+k-1,k) * C(n-3,k) / (k+1)
        auto c1 = binom_pe(n + k - 1, k);
        auto c2 = binom_pe(n - 3, k);

        long long den = k + 1;
        long long ed = 0;
        while (den % MOD == 0) {
            den /= MOD;
            ++ed;
        }

        long long et = c1.exp + c2.exp - ed;
        if (et > 0) {
            cout << 0 << '\n';
            continue;
        }

        // Integer guarantees et >= 0.
        long long ans = c1.unit;
        ans = ans * c2.unit % MOD;
        ans = ans * modinv(den % MOD) % MOD;

        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    }

    return 0;
}