概要

一列に並んだ \(N\) 個の区画から \(K\) 個の区画を選び、隣り合う区画を同時に選ばないようにする選び方の総数を求める問題です。

考察

隣り合う区画を選べない制約があるため、最大で選べる区画数は \(\lceil N/2 \rceil\) 個です。\(K\) がこれを超える場合は条件を満たす選び方が存在しないため、0 を出力します。

重要な観察として、この問題は「\(N\) 個の連続する区画から \(K\) 個の区画を選び、どの2つも隣り合わない」という条件は、組合せ数学における「隙間挿入法」で解くことができます。具体的には、選ばない \(N-K\) 個の区画を並べ、その隙間に選ぶ \(K\) 個の区画を挿入する方法を考えます。

\(N-K\) 個の「選ばない区画」があるとき、これらの隙間（両端を含む）は \(N-K+1\) 個あります。この \(N-K+1\) 個の隙間から \(K\) 個の隙間を選び、それぞれに1つずつ「選ぶ区画」を配置する方法を考えると、これが求める組合せになります。したがって、答えは \(\binom{N-K+1}{K}\) となります。

アルゴリズム

1. \(K > \lceil N/2 \rceil\) の場合は 0 を出力
2. それ以外の場合は、二項係数 \(\binom{N-K+1}{K}\) を計算
3. 前計算として階乗とその逆元を \(O(N)\) で計算し、二項係数を高速に計算できるようにする

計算量

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

階乗とその逆元の前計算に \(O(N)\) 時間・空間が必要です。二項係数の計算自体は \(O(1)\) で行えます。

実装のポイント

• モジュラ逆数の計算には拡張ユークリッドの互除法の代わりに、\(MOD\) が素数の場合に有効な Fermat の小定理に基づく方法（実際には線形時間で逆元テーブルを構築する方法）を使用

• 階乗（fact）、階乗の逆元（fact_inv）、逆元テーブル（inv）を前計算

• 二項係数関数 comb(n, r) では、\(r\) が範囲外の場合の処理を追加

• \(10^9+7\) での剰余計算を忘れずに行う

  ソースコード

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

この解説は deepseekv3 によって生成されました。