Number of Sets of K Non-Overlapping Line Segments

The most efficient solution involves reframing the problem from a dynamic programming perspective to a combinatorial one. The problem of choosing k non-overlapping line segments can be mapped to a problem of choosing 2k numbers from a specific range. This transformation, a variant of the 'stars and bars' method, leads to a direct mathematical formula for the answer, which can be computed very efficiently.

• Realize the problem is equivalent to a combinatorial selection problem.
• The condition 0 <= s_1 < e_1 <= s_2 < ... <= s_k < e_k <= n-1 can be transformed into a strictly increasing sequence 0 <= z_1 < z_2 < ... < z_{2k} <= n+k-2.
• This is equivalent to choosing 2k distinct numbers from the set {0, 1, ..., n+k-2}, which has n+k-1 elements.
• The number of ways is given by the binomial coefficient C(n+k-1, 2k).
• To compute C(N, K) mod P where P is prime, we use the formula (N! * inv(K!) * inv((N-K)!)) mod P.
• Precompute factorials and their modular inverses up to n+k-1.
• Calculate the final result using the precomputed values.

Let the k non-overlapping segments be [s_1, e_1], [s_2, e_2], ..., [s_k, e_k]. By the problem definition, we can order them such that: 0 <= s_1 < e_1 <= s_2 < e_2 <= ... <= s_k < e_k <= n-1

This is a sequence of 2k integers with a mix of strict (<) and non-strict (<=) inequalities. We can convert this into a problem of choosing 2k distinct integers by applying a transformation. Let's define a new sequence z_1, z_2, ..., z_{2k} as follows:

• z_1 = s_1
• z_2 = e_1
• z_3 = s_2 + 1
• z_4 = e_2 + 1
• ...
• z_{2i-1} = s_i + i - 1
• z_{2i} = e_i + i - 1

This transformation cleverly converts the original sequence into a strictly increasing sequence: 0 <= z_1 < z_2 < ... < z_{2k}.

The upper bound for z_{2k} is e_k + k - 1. Since e_k <= n-1, we have z_{2k} <= (n-1) + (k-1) = n+k-2.

So, the problem is now equivalent to choosing 2k distinct numbers from the range [0, n+k-2]. The total count of numbers in this range is (n+k-2) - 0 + 1 = n+k-1.

The number of ways to choose 2k distinct numbers from n+k-1 numbers is given by the binomial coefficient C(n+k-1, 2k).

We can compute C(N, K) = N! / (K! * (N-K)!) modulo 10^9 + 7. Since 10^9 + 7 is a prime number, we can precompute factorials and their modular inverses (using Fermat's Little Theorem) to find the answer efficiently.

class Solution {
    public int numberOfSets(int n, int k) {
        int MOD = 1_000_000_007;
        int N = n + k - 1;
        int K = 2 * k;
        
        if (K > N) {
            return 0;
        }

        // Calculate C(N, K) % MOD
        long[] fact = new long[N + 1];
        long[] invFact = new long[N + 1];
        fact[0] = 1;
        invFact[0] = 1;

        for (int i = 1; i <= N; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[N] = power(fact[N], MOD - 2, MOD);
        for (int i = N - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }

        long numerator = fact[N];
        long denominator = (invFact[K] * invFact[N - K]) % MOD;
        
        return (int) ((numerator * denominator) % MOD);
    }

    private long power(long base, long exp, int mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}