概要

隣り合う区画を同時に選ばないように、\(N\) 個の区画からちょうど \(K\) 個を選ぶ方法数を、組合せに帰着して \(10^9+7\) で求めます。

考察

「隣接禁止」なので、選んだ区画の間には必ず 1 つ以上の空き区画が必要です。
素朴に「左から順に選ぶ/選ばない」を DP すると、状態に「今までに何個選んだか」が必要になり \(O(NK)\) になり、\(N\le 10^6\) では到底間に合いません。

ここで重要な観察は、答えが 単純な組合せ \(\binom{N-K+1}{K}\) になることです。

なぜ \(\binom{N-K+1}{K}\) になるか

選ぶ区画を昇順に \(a_1 < a_2 < \dots < a_K\) とします。隣接禁止より [ a_{i+1} \ge a_i + 2 ] が必要です。

この「間に 1 個以上空ける」制約を消すために、次の変換をします： [ b_i = a_i - (i-1) ] すると - \(b_1 \ge 1\) - \(b_K \le N-(K-1)=N-K+1\) - さらに \(a_{i+1}\ge a_i+2\) から [ b{i+1} = a{i+1}-i \ge (a_i+2)-i = (a_i-(i-1)) + 1 = b_i + 1 ] よって \(b_1 < b_2 < \dots < b_K\)（単なる「相異なる \(K\) 個の数を選ぶ」）になります。

つまり、\(1\) から \(N-K+1\) の中から異なる \(K\) 個を選ぶことと 1 対 1 に対応するため、 [ \text{答え} = \binom{N-K+1}{K} ] です。

また、そもそも選べるためには最小配置（\(1,3,5,\dots\)）が入る必要があるので [ N \ge 2K-1 \iff N-K+1 \ge K ] が必要です。これを満たさないと答えは \(0\) になります（コードの if n < K:）。

（例）\(N=5, K=2\) のとき \(n=N-K+1=4\) なので答えは \(\binom{4}{2}=6\)。実際、選び方は
\(\{1,3\},\{1,4\},\{1,5\},\{2,4\},\{2,5\},\{3,5\}\) の 6 通りです。

アルゴリズム

1. \(n = N-K+1\) と置く。
2. もし \(n < K\) なら不可能なので \(0\) を出力。
3. そうでなければ答えは \(\binom{n}{K}\)。
4. \(\bmod = 10^9+7\) は素数なので、階乗と逆階乗を前計算して [ \binom{n}{K} \equiv \frac{n!}{K!(n-K)!} \pmod{\bmod} ] を計算する。
   • 逆元はフェルマーの小定理より \(a^{-1}\equiv a^{\bmod-2}\pmod{\bmod}\) を使い pow(a, MOD-2, MOD) で求める。

計算量

• 時間計算量: \(O(n)\)（階乗・逆階乗の前計算）
• 空間計算量: \(O(n)\)（fact, invfact 配列）

実装のポイント

• \(n = N-K+1\) までの階乗が必要なので、配列サイズは n+1。

• 逆階乗は invfact[n] = fact[n]^{-1} を 1 回だけ pow で求め、そこから [ (i-1)!^{-1} = i!^{-1}\cdot i ] を使って逆向きに埋めると高速です。

• 不可能条件 \(n<K\)（つまり \(N<2K-1\)）を最初に判定して早期終了します。

  ソースコード

import sys

MOD = 10**9 + 7

def modinv(a):
    return pow(a, MOD - 2, MOD)

def main():
    N, K = map(int, sys.stdin.readline().split())
    n = N - K + 1
    if n < K:
        print(0)
        return

    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD

    invfact = [1] * (n + 1)
    invfact[n] = modinv(fact[n])
    for i in range(n, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD

    ans = fact[n] * invfact[K] % MOD * invfact[n - K] % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。