数え上げ問題
C - Typical Stairs
O(N)
import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): MOD = 10**9+7 N, M = list(map(int, input().split())) ok = [False] * (N+1) dp = [0] * (N+1) dp[0] = 1 for _ in range(M): a = int(input()) ok[a] = True for i in range(1, N+1): if ok[i]: continue if i == 1: dp[i] = dp[i-1] else: dp[i] = (dp[i-1] + dp[i-2]) % MOD print(dp[N]) # エントリポイント if __name__ == '__main__': main()