Problem: There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.  However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

Submission attempts (in order):
# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
import numpy as np


def fib(n):
    a = (1 + np.sqrt(5)) / 2
    b = (1 - np.sqrt(5)) / 2
    ans = (a**n - b**n) / np.sqrt(5)
    return int(ans)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    length = len(broken_stairs)
    if length == 0:
        print(fib(N) % 1000000007)
        sys.exit()

    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = fib(N - 2 * length)
        print(ans % 1000000007)

# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) / 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)


# 2019 6/12

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

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

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

for i in range(2, N + 1):
    if i in broken:
        continue
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N] % MOD)

# 2019 6/12

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

dp = [0] * (N + 1)

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

for i in range(2, N + 1):
    if i in broken:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N-5:])

print(dp[N])

# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) % 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)


# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP
from sys import setrecursionlimit(1000000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

# 2019 6/9

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

from sys import setrecursionlimit
setrecursionlimit(100000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    # N, M = list(map(int, input().split()))
    
    
    
    #
    
    
    #     print(0)
    # else:
    
    

    tmp = 1
    num = [0, 22, 22, 22, 22, 11]
    for i in num:
        tmp += fib(i)
        print(tmp % 1000000007)


# 2019 6/12

# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

dp = [0] * (N + 1)

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

for i in range(2, N + 1):
    if i in broken:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted