HackerRank Combinatorics – To Infinity and Beyond – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: To Infinity and Beyond

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464834903

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/to-infinity-and-beyond/problem

Cerinta

Holly Bee lives at location $(0, 0, 0)$ in a *3D* Cartesian space and wants to go to Infinity, a tea shop franchise where each shop is located at some $(x_i, y_i, z_i)$. To get there, she must perform a series of *moves* in the following forms:

- *Walk*. This only applies when Holly is on the ground (i.e., when $z = 0$). If Holly is at $(x, y, 0)$, then she can go to either $(x + 1, y, 0)$ or $(x, y + 1, 0)$ in one move.  
- *Fly*. If Holly is at $(x,y,z)$, then she can go to $(X,Y,Z)$ as long as $x < X$, $y < Y$, and $z < Z$.  

Note that Holly Bee *must* be on a lattice point after each move.  

Holly Bee has $t$ Infinity shops near her meadow. She knows that there are many paths she can take to reach each Infinity shop, but she wants to know the *exact* number of paths she can take to each shop. Given the *3D* coordinates for $t$ Infinity shops, find and print the number of ways for Holly Bee to get to each shop on a new line. Recall that Holly Bee always starts at location $(0, 0, 0)$.

Input Format

The first line contains an integer, $t$, denoting the number of Infinity shops.  	
Each line $i$ of the $t$ subsequent lines describes the location of an Infinity tea shop in the form of three space-separated integers denoting the respective $x_i$, $y_i$, and $z_i$ values of the shop's location.

Output Format

For each Infinity tea shop location $i$, print the number of different paths from $(0,0,0)$ to $(x_i, y_i, z_i)$ using some sequence of *walk* and *fly* moves described above. As this number can be very large, your answer must be modulo $(10^9+7)$.

Constraints

For $\text{20%}$ of the maximum score:  

- $1 \le t \le 50$  
- $x_i, y_i, z_i \ge 1$  
- $x_i \times y_i \le 10^{6}$  
- $z_i \le 10^{12}$  

For the remaining $\text{80%}$ the maximum score:  

- $1 \le t \le 5$  
- $x_i, y_i, z_i \ge 1$  
- $x_i \times y_i \le 10^{12}$  
- $z_i \le 10^{12}$

Cod sursa

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

static const int MOD = 1000000007;

static inline int addmod(int a, int b) {
    int s = a + b;
    if (s >= MOD) s -= MOD;
    return s;
}

static inline int mulmod(long long a, long long b) {
    return int((a * b) % MOD);
}

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

    int T;
    cin >> T;
    vector<array<long long, 3>> q(T);
    long long maxX = 0;

    for (int i = 0; i < T; i++) {
        long long x, y, z;
        cin >> x >> y >> z;
        q[i] = {x, y, z};
        long long mn = min(x, y);
        if (mn > maxX) maxX = mn;
    }

    int LIM = (int)maxX;
    vector<int> inv(LIM + 1, 1);
    for (int i = 2; i <= LIM; i++) {
        inv[i] = MOD - int((MOD / i) * 1LL * inv[MOD % i] % MOD);
    }

    for (int tc = 0; tc < T; tc++) {
        long long x = q[tc][0], y = q[tc][1], z = q[tc][2];

        // z == 0: only walk moves on ground.
        if (z == 0) {
            // Number of monotone walks to (x,y,0) = C(x+y, x).
            // This branch is not needed for official constraints (z>=1), but kept for completeness.
            long long n = x + y;
            long long k = min(x, y);
            int c = 1;
            for (long long i = 1; i <= k; i++) {
                long long num = (n - (i - 1)) % MOD;
                c = mulmod(c, num);
                c = mulmod(c, inv[(int)i]);
            }
            cout << c << '\n';
            continue;
        }

        if (x > y) swap(x, y);
        int X = (int)x;
        long long Y = y;

        vector<int> h(X + 1, 0), suf(X + 2, 0);

        int cx = 1; // C(X,0)
        int cy = 1; // C(Y,0)
        h[0] = 1;
        for (int i = 1; i <= X; i++) {
            cx = mulmod(cx, (X - i + 1));
            cx = mulmod(cx, inv[i]);

            long long numY = (Y - i + 1) % MOD;
            if (numY < 0) numY += MOD;
            cy = mulmod(cy, numY);
            cy = mulmod(cy, inv[i]);

            h[i] = mulmod(cx, cy);
        }

        for (int i = X; i >= 0; i--) {
            suf[i] = addmod(suf[i + 1], h[i]);
        }

        int lim = (int)min<long long>(X, z);
        int combZ = 1; // C(z-1,0)
        int ans = 0;

        for (int k = 1; k <= lim; k++) {
            ans = (ans + 1LL * combZ * suf[k]) % MOD;

            if (k < lim) {
                long long num = (z - k) % MOD; // for next: C(z-1,k) from C(z-1,k-1)
                if (num < 0) num += MOD;
                combZ = mulmod(combZ, num);
                combZ = mulmod(combZ, inv[k]);
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

HackerRank Combinatorics – To Infinity and Beyond