Overview

This is a dynamic programming (DP) problem where you count the number of ways to climb an \(N\)-step staircase using steps of \(1\), \(2\), or \(3\) at a time, under the constraint that you cannot land on broken steps.

Analysis

Key Insight

First, let’s consider the case where there are no broken steps. If we let \(dp[i]\) be the number of ways to reach step \(i\) from step \(0\), then to arrive at step \(i\), there are \(3\) possible previous states: “climb \(1\) step from step \(i-1\),” “climb \(2\) steps from step \(i-2\),” and “climb \(3\) steps from step \(i-3\).” Therefore:

\[dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\]

This recurrence holds. This structure is similar to the so-called “Tribonacci sequence.”

Handling Broken Steps

Since you cannot land on a broken step \(i\), we simply set \(dp[i] = 0\). Since you also cannot depart from a broken step, all routes passing through that step automatically become \(0\), which is correctly reflected in the computation of subsequent steps.

Concrete Example (\(N = 5\), broken steps \(= \{2\}\))

Step \(i\)	Broken?	Computation of \(dp[i]\)	\(dp[i]\)
0	No	Initial value	1
1	No	\(dp[0] = 1\)	1
2	Yes	Broken, so \(0\)	0
3	No	\(dp[2] + dp[1] + dp[0] = 0 + 1 + 1\)	2
4	No	\(dp[3] + dp[2] + dp[1] = 2 + 0 + 1\)	3
5	No	\(dp[4] + dp[3] + dp[2] = 3 + 2 + 0\)	5

The answer is \(dp[5] = 5\). We can confirm that there are \(5\) ways to climb while avoiding step \(2\).

Comparison with a Naive Approach

If we recursively enumerate all ways to climb, the branching grows exponentially, and for large \(N\) (up to \(10^5\)), this is far too slow. Using DP, each step can be computed in \(O(1)\), giving an overall complexity of \(O(N)\).

Algorithm

1. Store the broken step numbers in a set (set) (to allow \(O(1)\) lookups).
2. Prepare an array \(dp[0..N]\) and initialize with \(dp[0] = 1\) (there is exactly \(1\) way to be on the ground).
3. For \(i = 1\) to \(N\), do the following:
   • If \(i\) is a broken step, set \(dp[i] = 0\).
   • Otherwise, compute \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\) (without adding terms where the index is less than \(0\)), taken modulo \(10^9 + 7\).
4. Output \(dp[N]\).

Complexity

• Time complexity: \(O(N + M)\) (building the set of broken steps takes \(O(M)\), and the DP loop takes \(O(N)\))
• Space complexity: \(O(N + M)\) (\(O(N)\) for the DP array, \(O(M)\) for the set of broken steps)

Implementation Notes

• To check whether a step is broken efficiently, use a set (set) instead of a list. The in operation on a list is \(O(M)\), but for a set it is \(O(1)\) on average.

• When \(M = 0\), the second line of input may not be provided, so it is safer to read all input at once and use split().

• When \(i < 2\) or \(i < 3\), guard with conditional checks to avoid referencing non-existent indices.

• Since the answer can become very large, don’t forget to take the remainder modulo \(10^9 + 7\) at every step.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    broken = set()
    for i in range(M):
        broken.add(int(input_data[idx])); idx += 1
    
    MOD = 10**9 + 7
    
    dp = [0] * (N + 1)
    dp[0] = 1
    
    for i in range(1, N + 1):
        if i in broken:
            dp[i] = 0
        else:
            dp[i] = dp[i - 1]
            if i >= 2:
                dp[i] += dp[i - 2]
            if i >= 3:
                dp[i] += dp[i - 3]
            dp[i] %= MOD
    
    print(dp[N])

main()

---

This editorial was generated by claude4.6opus-thinking.