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

  • Problemă: Beautiful Sets
  • Domeniu: Combinatorics
  • Limbaj: C++14

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

Cerință

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 ≤ q ≤ 10
* 1 ≤ n ≤ 10^6
* 1 ≤ k ≤ n

Subtasks

* 1 ≤ n ≤ 1000 for 40% of the maximum score.

Cod sursă

#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;
}
HackerRank Combinatorics – Beautiful Sets