Overview

A problem of finding the number of ways to choose \(K\) non-adjacent sections from \(N\) sections.

Analysis

This problem has the constraint that “adjacent sections cannot be selected at the same time.” For example, when \(N = 5\), \(K = 2\), selections like \(\{1, 3\}\) or \(\{2, 5\}\) are OK, but \(\{1, 2\}\) is NG.

A naive approach would be to enumerate all combinations and exclude those that don’t satisfy the condition, but this is computationally infeasible. Another approach using dynamic programming (DP) could be considered, but since the constraint is as large as \(N \leq 10^6\), a DP with time complexity \(O(NK)\) would not be fast enough.

The key observation is that the problem of “choosing \(K\) non-adjacent elements” can be solved using combinatorics. Specifically, since there must be at least one “empty section” between each pair of trees, there must be at least one gap between any two trees.

In other words, imagine placing the “sections without trees” first, and then inserting trees into the gaps between them. For example, when \(N=5\), \(K=2\), there are \(5 - 2 = 3\) sections without trees, and we place trees into the “gaps” created by these sections. Note that gaps also exist at the beginning and end.

Generalizing this idea, the answer is the number of ways to choose \(K\) from \(N - K + 1\) “candidate gaps,” which is \(_{N-K+1}C_{K}\).

However, if \(K > \frac{N+1}{2}\), it is impossible to choose \(K\) sections without any being adjacent, so the answer is \(0\).

Algorithm

1. First, if \(K > \left\lfloor \frac{N+1}{2} \right\rfloor\), the answer is \(0\).
2. Otherwise, compute the combination \(_{N-K+1}C_K\).
3. For computing combinations, precompute factorials and their modular inverses for fast calculation.

Specifically: - fact[i]: \(i! \bmod (10^9+7)\) - factinv[i]: \((i!)^{-1} \bmod (10^9+7)\) - comb(n, r) function computes \(_nC_r = \frac{n!}{r!(n-r)!}\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Precompute factorials and their modular inverses for fast combination calculation.

• Since the numerator and denominator values become very large when computing combinations, perform mod operations appropriately.

• Use pow(a, MOD-2, MOD) to compute modular inverses (Fermat’s little theorem).

• There is no need to take mod before outputting with print(ans) to ensure the answer is non-negative (in Python, it won’t be negative).

  Source Code

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    N, K = map(int, input().split())
    
    if K > (N + 1) // 2:
        print(0)
        return
    
    # dp[i][j] = i個の区画を使ってj個選ぶ方法
    # ただし、i個の区画でj個選ぶとき、最後の区画を選んでも選ばなくてもよい
    # より効率的にするために組み合わせで解く
    
    # 組み合わせの前計算
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
        
    def modinv(a):
        return pow(a, MOD-2, MOD)
    
    factinv = [1] * (max_n + 1)
    factinv[max_n] = modinv(fact[max_n])
    for i in range(max_n - 1, -1, -1):
        factinv[i] = factinv[i+1] * (i+1) % MOD
    
    def comb(n, r):
        if r < 0 or r > n:
            return 0
        return fact[n] * factinv[r] % MOD * factinv[n-r] % MOD
    
    # 1からNまでにK個選んで隣接しないようにする
    # これは、N-K+1個の隙間にK個の植木を配置するのと同じ（最初と最後も含む）
    # つまり、N-K+1個からK個を選ぶ組み合わせ
    ans = comb(N - K + 1, K)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.