概要

\(N\) 個の区画から隣接しないように \(K\) 個を選ぶ組み合わせの数を求める問題。

考察

この問題では「隣り合う区画を同時に選んではいけない」という制約があります。
例えば \(N = 5\), \(K = 2\) のとき、区画の選び方は例えば \(\{1, 3\}\) や \(\{2, 5\}\) はOKですが、\(\{1, 2\}\) はNGです。

素朴な方法として、全組み合わせから条件を満たさないものを除くことを考えられますが、これは計算量的に不可能です。
また、動的計画法（DP）による解法も考えられますが、制約が \(N \leq 10^6\) と大きいため、計算量 \(O(NK)\) のDPでは間に合いません。

重要な観察は、「隣接しない \(K\) 個の要素を選ぶ」問題は、組み合わせを用いて解けるということです。
具体的には、\(K\) 個の植木の間に最低でも1つの「空き区画」が必要なので、植木同士の間には1つ以上の隙間が必要になります。

言い換えれば、「植木を置かない区画」をあらかじめ配置しておき、その隙間に植木を入れるイメージです。
例えば、\(N=5\), \(K=2\) のとき、植木を置かない区画は \(5 - 2 = 3\) 個あり、これらによって作られる「隙間」に植木を配置します。
ただし、最初と最後にも隙間が存在することに注意します。

このような考え方を一般化すると、\(N - K + 1\) 個の「隙間候補」から \(K\) 個を選ぶ組み合わせ、つまり \(_{N-K+1}C_{K}\) が答えになります。

ただし、もし \(K > \frac{N+1}{2}\) であれば、隣接しないように \(K\) 個を選ぶことは不可能なので、答えは \(0\) です。

アルゴリズム

1. まず、\(K > \left\lfloor \frac{N+1}{2} \right\rfloor\) なら答えは \(0\)。
2. そうでない場合は、組み合わせ \(_{N-K+1}C_K\) を求めます。
3. 組み合わせの計算には、事前に階乗とその逆元を前計算しておき、高速に計算します。

具体的には： - fact[i]: \(i! \bmod (10^9+7)\) - factinv[i]: \((i!)^{-1} \bmod (10^9+7)\) - comb(n, r) 関数で \(_nC_r = \frac{n!}{r!(n-r)!}\) を計算

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 組み合わせを高速に計算するために、階乗とその逆元を前計算しておくこと。

• 組み合わせの計算時に、分子・分母それぞれの値が非常に大きくなるため、mod演算を適切に行うこと。

• pow(a, MOD-2, MOD) を使って逆元を計算する（フェルマーの小定理）。

• 最後に答えが負にならないよう、print(ans) で出力する前に mod を取る必要はない（Pythonでは負にならない）。

  ソースコード

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()

この解説は qwen3-coder-480b によって生成されました。