Overview

This is a problem of counting the number of ways to choose \(K\) sections from \(N\) sections such that no two chosen sections are adjacent. This is a classic combinatorics problem that can be reduced to the binomial coefficient \(\binom{N-K+1}{K}\).

Analysis

Key Insight: Counting Non-Adjacent Selections

Directly counting the number of ways to choose \(K\) sections from \(N\) sections such that “no two are adjacent” seems difficult at first glance. However, using a well-known transformation technique, we can reduce it to a standard binomial coefficient.

Transformation Idea

Let the positions of the \(K\) chosen sections, sorted from left to right, be \(p_1 < p_2 < \cdots < p_K\). The non-adjacency condition is \(p_{i+1} - p_i \geq 2\) (for each \(i\)).

Now, define new variables \(q_i = p_i - (i - 1)\). Then:

• The \(q_i\) are strictly increasing with \(q_{i+1} - q_i = (p_{i+1} - p_i) - 1 \geq 1\), so \(q_1 < q_2 < \cdots < q_K\)
• The range of \(q_i\) is \(1 \leq q_i \leq N - (K - 1)\)

In other words, this establishes a one-to-one correspondence with freely choosing \(K\) sections from \(N - K + 1\) sections (without any adjacency constraint).

Concrete Example

When \(N = 5, K = 2\), we get \(\binom{5 - 2 + 1}{2} = \binom{4}{2} = 6\) ways.

Enumerating them explicitly, we have \(\{1,3\}, \{1,4\}, \{1,5\}, \{2,4\}, \{2,5\}, \{3,5\}\) — exactly \(6\) ways, which matches.

Issues with Naive Approaches

While it is possible to solve this with DP or brute-force search, \(N\) can be up to \(10^6\), so an \(O(NK)\) DP may not be fast enough. By reducing to a binomial coefficient, we can compute the answer in \(O(N)\).

Algorithm

1. Let \(M = N - K + 1\)
2. If \(M < K\) or \(K < 0\), the answer is \(0\) (it is impossible to make a valid selection)
3. Otherwise, compute \(\binom{M}{K} \mod (10^9 + 7)\)

To compute the binomial coefficient, we use precomputed factorials and modular inverses:

\[\binom{M}{K} = \frac{M!}{K! \cdot (M-K)!}\]

Modular inverses are computed using Fermat’s little theorem: \(a^{-1} \equiv a^{p-2} \pmod{p}\) (where \(p\) is prime). The inverse factorial table can be efficiently constructed by filling it from the end using multiplication.

Complexity

• Time complexity: \(O(N)\) (building the factorial table and the inverse factorial table each take \(O(N)\))
• Space complexity: \(O(N)\) (storing the factorial table and inverse factorial table)

Implementation Notes

• When \(M = N - K + 1 < K\) (i.e., \(K > \frac{N+1}{2}\)), no matter how you choose, some sections will be adjacent, so the answer is \(0\). Don’t forget this check.

• For the inverse factorial table, first compute \(\text{inv\_fact}[M]\) as \(\text{fact}[M]^{p-2} \mod p\), then compute \(\text{inv\_fact}[i] = \text{inv\_fact}[i+1] \times (i+1) \mod p\) in descending order. This way, only one modular exponentiation is needed, making it efficient.

• Perform \(\mod 10^9 + 7\) operations at each step to prevent overflow (in Python, this is not strictly necessary due to arbitrary-precision integers, but it is done for speed).

  Source Code

import sys

def solve():
    input_data = sys.stdin.readline().split()
    N = int(input_data[0])
    K = int(input_data[1])
    
    MOD = 10**9 + 7
    
    # We need to choose K non-adjacent positions from N positions.
    # This is equivalent to C(N - K + 1, K).
    # 
    # Explanation: if we place K items in N slots with no two adjacent,
    # we can think of it as placing K items and (N-K) gaps. 
    # Between each pair of adjacent chosen items, there must be at least one gap.
    # This transforms to choosing K positions from (N - K + 1) positions.
    
    M = N - K + 1
    
    if M < K or K < 0:
        print(0)
        return
    
    # Compute C(M, K) mod MOD
    # M can be up to 10^6, K can be up to 10^6
    # Precompute factorials and inverse factorials
    
    max_val = M
    if max_val < 0:
        print(0)
        return
    
    # Precompute factorial and inverse factorial
    fact = [1] * (max_val + 1)
    for i in range(1, max_val + 1):
        fact[i] = fact[i - 1] * i % MOD
    
    inv_fact = [1] * (max_val + 1)
    inv_fact[max_val] = pow(fact[max_val], MOD - 2, MOD)
    for i in range(max_val - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    
    ans = fact[M] * inv_fact[K] % MOD * inv_fact[M - K] % MOD
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.