## The problem We are given `n` points sitting on a line at coordinates `0, 1, ..., n-1`. I have to draw exactly `k` line segments. Each segment connects two of those points, so it needs at least two distinct endpoints, and no two segments may overlap. Overlap here means sharing more than a single point: two segments touching at one endpoint is allowed, but they cannot share any interior stretch. I return how many distinct sets of `k` such segments exist, modulo `1e9 + 7`. ## First instinct: a DP My first working idea was a two-dimensional DP walking left to right over the points, carrying how many segments were already placed and whether the point I am standing on is free to start a new segment or is the right end of one that just closed. That gives an `O(n * k)` table and it passes. But while checking small cases by hand I noticed the counts lined up suspiciously with binomial coefficients, so I went looking for the closed form instead. ## The bijection Here is the observation that collapses everything. A valid configuration of `k` non-overlapping segments is completely described by `2k` endpoint values, read left to right: `a1 <= b1 <= a2 <= b2 <= ... <= ak <= bk`. The relation between a segment's own two ends must actually be strict (`a < b`, a segment can't be a single point), and consecutive segments may touch (`b_i = a_{i+1}` is fine). So I have a chain of `2k` values from the range `0 .. n-1` that is weakly increasing overall, but with `k` of the gaps forced to be strict. The standard trick for turning "some steps must strictly increase" into "all steps weakly increase" is to shift: add `1` to every value after each strict step. That expands the usable range from `n` up to `n + k - 1`, and now I am simply choosing `2k` values out of `n + k - 1` with no constraints at all. ## The formula That is exactly a combination: the answer is `C(n + k - 1, 2k)`. I sanity-checked it against the examples. For `n = 4, k = 2` it gives `C(5, 4) = 5`. For `n = 3, k = 1` it gives `C(3, 2) = 3`. For `n = 30, k = 7` it gives `796297179`. All three match, and I also brute-forced every `n` up to 9 against an explicit enumeration to be sure the bijection was not off by one anywhere. ## Computing it With `n, k <= 1000`, the top of the binomial is at most about `2000`, so I precompute factorials up to `m = n + k - 1` and their modular inverses via one Fermat exponentiation, then read off `C(m, 2k)` in constant time. If `2k > m` the answer is `0`, which also covers the degenerate inputs cleanly. ```cpp class Solution { public: int numberOfSets(int n, int k) { // A configuration of k non-overlapping segments on n collinear points // (segments may share endpoints but not overlap in their interior) is in // bijection with choosing 2k marks out of n+k-1 slots, so the answer is // the closed form C(n+k-1, 2k) (mod 1e9+7). const long long MOD = 1e9 + 7; int m = n + k - 1, r = 2 * k; if (r > m) return 0; vector fact(m + 1), inv(m + 1); fact[0] = 1; for (int i = 1; i <= m; ++i) fact[i] = fact[i - 1] * i % MOD; auto power = [&](long long b, long long e) { long long res = 1; b %= MOD; while (e) { if (e & 1) res = res * b % MOD; b = b * b % MOD; e >>= 1; } return res; }; inv[m] = power(fact[m], MOD - 2); for (int i = m; i > 0; --i) inv[i - 1] = inv[i] * i % MOD; return (int)(fact[m] * inv[r] % MOD * inv[m - r] % MOD); } }; ``` ## Complexity Building the factorial and inverse-factorial tables is `O(n + k)` time and space, and the single modular exponentiation for the inverse adds an `O(log MOD)` factor. Everything else is a couple of multiplications. Runtime came back as `0 ms` (100th percentile) with `9.7 MB` of memory.