Overview

This is a problem of selecting \(K\) plots from \(N\) plots arranged in a row, such that no two selected plots are adjacent, and finding the total number of ways to do so.

Analysis

Due to the constraint that adjacent plots cannot be selected, the maximum number of plots that can be selected is \(\lceil N/2 \rceil\). If \(K\) exceeds this, there is no valid selection, so we output 0.

An important observation is that the condition “select \(K\) plots from \(N\) consecutive plots such that no two are adjacent” can be solved using the “gap insertion method” in combinatorics. Specifically, we consider arranging the \(N-K\) unselected plots and inserting the \(K\) selected plots into the gaps between them.

When there are \(N-K\) “unselected plots,” there are \(N-K+1\) gaps (including both ends). By choosing \(K\) gaps from these \(N-K+1\) gaps and placing one “selected plot” in each, we obtain the desired combination. Therefore, the answer is \(\binom{N-K+1}{K}\).

Algorithm

1. If \(K > \lceil N/2 \rceil\), output 0
2. Otherwise, compute the binomial coefficient \(\binom{N-K+1}{K}\)
3. As preprocessing, compute factorials and their modular inverses in \(O(N)\) to enable fast binomial coefficient computation

Complexity

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

Precomputing factorials and their inverses requires \(O(N)\) time and space. The binomial coefficient computation itself can be done in \(O(1)\).

Implementation Notes

• For computing modular inverses, instead of the extended Euclidean algorithm, we use a method based on Fermat’s little theorem which is effective when \(MOD\) is prime (specifically, building an inverse table in linear time)

• Precompute factorials (fact), inverse factorials (fact_inv), and an inverse table (inv)

• In the binomial coefficient function comb(n, r), add handling for when \(r\) is out of range

• Don’t forget to perform modular arithmetic with \(10^9+7\)

  Source Code

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().split()
    N = int(data[0])
    K = int(data[1])
    
    if K > (N + 1) // 2:
        print(0)
        return
        
    nCr = [0] * (N + 1)
    inv = [0] * (N + 1)
    fact = [0] * (N + 1)
    fact_inv = [0] * (N + 1)
    
    fact[0] = fact[1] = 1
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        fact[i] = fact[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD
        
    def comb(n, r):
        if r < 0 or r > n:
            return 0
        return fact[n] * fact_inv[r] % MOD * fact_inv[n - r] % MOD
        
    ans = comb(N - K + 1, K)
    print(ans % MOD)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.