概要

\(N\) 個の区画から隣り合わないように \(K\) 個を選ぶ方法の数を求める問題です。組合せ論の定番問題であり、二項係数 \(\binom{N-K+1}{K}\) に帰着できます。

考察

重要な気づき：隣り合わない選び方の数え上げ

\(N\) 個の区画から \(K\) 個を「隣り合わないように」選ぶ方法の数を直接数えるのは大変そうに見えます。しかし、有名な変換テクニックを使うと、通常の二項係数に帰着できます。

変換のアイデア

選んだ \(K\) 個の区画の位置を左から \(p_1 < p_2 < \cdots < p_K\) とします。隣り合わない条件は \(p_{i+1} - p_i \geq 2\)（各 \(i\)）です。

ここで、新しい変数 \(q_i = p_i - (i - 1)\) と置きます。すると：

• \(q_i\) は単調増加で \(q_{i+1} - q_i = (p_{i+1} - p_i) - 1 \geq 1\) となり、\(q_1 < q_2 < \cdots < q_K\)
• \(q_i\) の取りうる範囲は \(1 \leq q_i \leq N - (K - 1)\)

つまり、\(N - K + 1\) 個の区画から \(K\) 個を自由に（隣接制約なしで）選ぶことと一対一に対応します。

具体例

\(N = 5, K = 2\) のとき、\(\binom{5 - 2 + 1}{2} = \binom{4}{2} = 6\) 通りです。

実際に列挙すると、\(\{1,3\}, \{1,4\}, \{1,5\}, \{2,4\}, \{2,5\}, \{3,5\}\) の \(6\) 通りで一致します。

素朴なアプローチの問題

DPや全探索で解くことも可能ですが、\(N\) が最大 \(10^6\) なので、\(O(NK)\) のDPでは間に合わない場合があります。二項係数に帰着すれば \(O(N)\) で計算できます。

アルゴリズム

1. \(M = N - K + 1\) とする
2. \(M < K\) または \(K < 0\) ならば答えは \(0\)（選びようがない）
3. そうでなければ、\(\binom{M}{K} \mod (10^9 + 7)\) を計算する

二項係数の計算には、階乗の前計算とモジュラ逆元を使います：

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

モジュラ逆元はフェルマーの小定理を利用し、\(a^{-1} \equiv a^{p-2} \pmod{p}\)（\(p\) は素数）で求めます。逆元の階乗テーブルは末尾から掛け算で埋めることで効率的に構築できます。

計算量

• 時間計算量: \(O(N)\)（階乗テーブルの構築と逆元テーブルの構築がそれぞれ \(O(N)\)）
• 空間計算量: \(O(N)\)（階乗テーブルと逆階乗テーブルの格納）

実装のポイント

• \(M = N - K + 1 < K\) のとき（つまり \(K > \frac{N+1}{2}\)）は、どう選んでも隣り合ってしまうため答えは \(0\)。この判定を忘れないようにする

• 逆階乗テーブルは、まず \(\text{inv\_fact}[M]\) を \(\text{fact}[M]^{p-2} \mod p\) で求め、\(\text{inv\_fact}[i] = \text{inv\_fact}[i+1] \times (i+1) \mod p\) と降順に計算すると、べき乗計算が \(1\) 回で済み効率的

• \(\mod 10^9 + 7\) の演算を各ステップで行い、オーバーフローを防ぐ（Python では多倍長整数があるため必須ではないが、速度のために行う）

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。