HackerRank Combinatorics – Beautiful Sets

Challenge: Beautiful Sets

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 75.0 / 75

Submission status: Accepted

Submission score: 1.0

Submission ID: 464758111

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/polita-sets/problem

Cerinta

Consider a set, $S$, consisting of $k$ integers. The set is *beautiful* if *at least one* of the following conditions holds true for every $x \in S$:

1. $x-1 \in S$
2. $x+1 \in S$

For example, $S = \{1, 2, 50, 51\}$ is *beautiful* but $S = \{1, 5, 9\}$ is *not beautiful*. Given two integers, $n$ and $k$, can you find the number of different $k$-element beautiful sets you can create using integers $\in [1, n]$?

Perform $q$ queries where each query $i$ consists of some $n_i$ and $k_i$. For each query:

- Find the number of different beautiful sets having exactly $k$ elements that can be generated using integers in the inclusive range from $1$ to $n$. 
- Print the number of beautiful sets, modulo $10^9+7$, on a new line.

Input Format

The first line contains an integer, $q$, denoting the number of queries.	
Each line $i$ of the $q$ subsequent lines consists of two space-separated positive integers describing the respective values of $n_i$ and $k_i$ for the query.

Output Format

For each query, print the number of different beautiful sets of size $k$ that can be generated using integers in the inclusive range from $1$ to $n$ on a new line. As the answers to these queries can be quite large, each answer must be modulo $10^9+7$.

Constraints

* $1 \le q \le 10$   
* $1 \le n \le 10^6$ 
* $1 \le k \le n$  

**Subtasks**

* $1 \le n \le 1000$  for $40\%$ of the maximum score.

Cod sursa

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

static const long long MOD = 1000000007LL;

long long modPow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (__int128)r * a % MOD;
        a = (__int128)a * a % MOD;
        e >>= 1;
    }
    return r;
}

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

    int q;
    cin >> q;
    vector<pair<int, int>> qs(q);
    int maxN = 0;
    for (int i = 0; i < q; ++i) {
        int n, k;
        cin >> n >> k;
        qs[i] = {n, k};
        maxN = max(maxN, n);
    }

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

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

    for (auto qv : qs) {
        int n = qv.first;
        int k = qv.second;
        if (k <= 1) {
            cout << 0 << '\n';
            continue;
        }

        long long ans = 0;
        int rMax = min(k / 2, n - k + 1);
        for (int r = 1; r <= rMax; ++r) {
            long long waysBlocks = C(k - r - 1, r - 1); // split k ones into r runs, each >=2
            long long waysPlace = C(n - k + 1, r);       // place r runs in n slots
            ans = (ans + (__int128)waysBlocks * waysPlace) % MOD;
        }

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

    return 0;
}