概要

壊れている段には着地できない条件のもとで、\(0\) 段目から \(N\) 段目まで「1/2/3 段ずつ」上る方法の数を、\(10^9+7\) で割った余りで求めます。

考察

1 回の移動で進めるのは最大 3 段なので、ある段 \(i\) に到達する直前にいた可能性があるのは \(i-1, i-2, i-3\) のみです。
つまり、「段 \(i\) に到達する方法の数」は「段 \(i-1,i-2,i-3\) に到達する方法の数の和」になります（ただし段 \(i\) が壊れていない場合）。

素朴に「全ての上り方（移動列）を列挙する」ような再帰をすると、分岐が 3 通りずつ増えるため、計算量が指数時間になり \(N \le 10^5\) では間に合いません（TLE）。
そこで、同じ段への到達方法数を何度も計算しないように、各段について一度だけ計算して保存する動的計画法（DP）を使います。

また壊れている段は「着地できない」ので、その段への到達方法数は常に \(0\) として扱えばよいです（飛び越えるのはOK）。

例：\(N=5\)、壊れた段が \(\{2\}\) のとき
- \(dp[0]=1\)（地面にいる方法は 1 通り） - \(dp[1]=dp[0]=1\) - \(dp[2]=0\)（壊れているので着地不可） - \(dp[3]=dp[2]+dp[1]+dp[0]=0+1+1=2\) - \(dp[4]=dp[3]+dp[2]+dp[1]=2+0+1=3\) - \(dp[5]=dp[4]+dp[3]+dp[2]=3+2+0=5\)

アルゴリズム

\(dp[i]\) を「段 \(i\) に到達する方法の数」と定義します。

• 初期値：\(dp[0]=1\)
• 遷移：
  • もし段 \(i\) が壊れているなら \(dp[i]=0\)
  • そうでなければ
    \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)
    （ただし \(i-2<0\) や \(i-3<0\) の項は存在しないので加えない）
• 各 \(dp[i]\) は都度 \(10^9+7\) で割った余りを取る

最後に \(dp[N]\) を出力します。

計算量

• 時間計算量: \(O(N + M)\)（壊れた段の登録が \(O(M)\)、DP が \(O(N)\)）
• 空間計算量: \(O(N)\)（壊れ判定配列と DP 配列）

実装のポイント

• 壊れている段を高速に判定するため、長さ \(N+1\) の boolean 配列 broken を用意します。

• \(M=0\) のとき 2 行目が存在しないので、sys.stdin.read().split() のようにまとめて入力を読むと安全です。

• 遷移で参照するのは最大 3 つ前までなので、境界（\(i=1,2\)）では存在する分だけ足します。

• 壊れている段は必ず \(dp[i]=0\) とすることで、「その段に着地する経路」を自然に排除できます。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    broken = [False] * (N + 1)
    for _ in range(M):
        b = int(next(it))
        if 0 <= b <= N:
            broken[b] = True

    dp = [0] * (N + 1)
    dp[0] = 1

    for i in range(1, N + 1):
        if broken[i]:
            dp[i] = 0
        else:
            s = dp[i - 1]
            if i >= 2:
                s += dp[i - 2]
            if i >= 3:
                s += dp[i - 3]
            dp[i] = s % MOD

    print(dp[N] % MOD)

if __name__ == "__main__":
    main()

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