Overview

This problem asks us to find the total number of paths to reach step \(N\), given that each move can advance 1 to 3 steps, while avoiding specific “broken steps.”

Analysis

1. Considering State Transitions

To reach a given step \(i\), we consider which step we were on immediately before. Based on the problem rules, there are three possibilities: - Climb 1 step from step \(i-1\) - Climb 2 steps from step \(i-2\) - Climb 3 steps from step \(i-3\)

Therefore, the number of ways to reach step \(i\) is the sum of the number of ways to reach steps \(i-1\), \(i-2\), and \(i-3\).

2. Handling Broken Steps

If step \(i\) is broken, we cannot “land” on it. In other words, the number of ways to reach a broken step must be treated as 0.

3. Applying Dynamic Programming (DP)

The property that “the current state is determined by accumulation of past states” makes dynamic programming (DP) very effective. If we try to compute this with a naive recursive function, we end up recalculating the same steps many times, causing the computation to explode (it won’t finish in time for \(N=10^5\)). However, by recording (memoizing) results in order from smaller step numbers, we can compute efficiently.

Algorithm

Dynamic Programming Procedure

1. DP Table Definition: Define dp[i] as “the number of ways to reach step \(i\).” The array size is \(N+1\).
2. Initial Value Setting:
   • There is exactly 1 way to be on the ground (step 0), which is “do nothing,” so we set dp[0] = 1.
3. Preprocessing Broken Steps:
   • Create a boolean array is_broken of size \(N+1\) so that we can quickly determine whether a step is broken.
4. Computing the Transition: Compute the following in order from \(i = 1\) to \(N\):
   • If is_broken[i] is true, then dp[i] = 0
   • Otherwise, dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % (10^9 + 7) (※ Be careful that \(i-2\) or \(i-3\) do not go below 0)

Finally, the value of dp[N] is the answer.

Complexity

• Time Complexity: \(O(N)\)
  • Recording broken steps takes \(O(M)\), and the loop from step 1 to step \(N\) takes \(O(N)\). Since \(M \leq N\), the overall complexity is \(O(N)\), which is sufficiently fast for the constraint \(N=10^5\).
• Space Complexity: \(O(N)\)
  • The DP table and the array for managing broken steps use \(O(N)\) memory.

Implementation Notes

• Handling Large Numbers: Since the answer can become very large, take the remainder modulo \(10^9 + 7\) at each step of the computation. Python can handle arbitrary-precision integers, but taking the remainder frequently prevents slowdowns in computation speed.

• Fast Input: Since \(N\) and \(M\) can be large, it is efficient to read all input at once using methods like sys.stdin.read().split().

• Boundary Conditions: When \(i=1\) or \(i=2\), referencing dp[i-2] or dp[i-3] could cause index errors, so handle this with conditional branching.

  Source Code

import sys

def solve():
    # 入力を一括で取得して分割
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 階段の段数, M: 壊れている段の数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 壊れている段を記録する配列（高速アクセスのため）
    is_broken = [False] * (n + 1)
    if m > 0:
        for i in range(m):
            broken_step = int(input_data[2 + i])
            is_broken[broken_step] = True
            
    # DPテーブルの初期化
    # dp[i] は i段目に到達する方法の数
    dp = [0] * (n + 1)
    dp[0] = 1 # 地面（0段目）にいる方法は1通り
    
    MOD = 10**9 + 7
    
    # 1段目からN段目まで順番に計算
    for i in range(1, n + 1):
        if is_broken[i]:
            dp[i] = 0
            continue
        
        # 1歩前、2歩前、3歩前から到達可能
        ways = dp[i-1]
        if i >= 2:
            ways += dp[i-2]
        if i >= 3:
            ways += dp[i-3]
        
        # 10^9 + 7 で割った余りを格納
        dp[i] = ways % MOD
        
    # N段目に到達する方法の数を出力
    print(dp[n])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.