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

  • Problemă: To Infinity and Beyond
  • Domeniu: Combinatorics
  • Limbaj: C++14

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

Cerință

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 ≤ t ≤ 50
- x_i, y_i, z_i ≥ 1
- x_i × y_i ≤ 10^6
- z_i ≤ 10^12

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

- 1 ≤ t ≤ 5
- x_i, y_i, z_i ≥ 1
- x_i × y_i ≤ 10^12
- z_i ≤ 10^12

Cod sursă

#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