Problem:


Score : 300 points

Problem Statement

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.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9 + 7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))


def main():
    n,m = LI()
    a = [I() for _ in range(m)] + [inf]
    b = 0
    c = 1
    ai = 0
    for i in range(1,n+1):
        if a[ai] == i:
            ai += 1
            b,c = c,0
        else:
            b,c = c,b+c
            c %= mod

    return c


print(main())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())

mod = 10 ** 9 + 7

dp = [0] * 100010

j = 0
dp[0] = 1
if M > 0:
    if a[0] == 1:
        dp[1] = 0
        j += 1
    else:
        dp[1] = 1
else:
    dp[1] = 1

a += [-1]
for i in range(2, N+1):
    if M > 0:
        if i == a[j]:
            dp[i] = 0
            j += 1
            continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
a=[False]*100001
for i in range(m):
    a[int(input())]=True

ans=[0]*100001
ans[0]=1
if a[1]:
    ans[1]=0
else:
    ans[1]=1

for i in range(2,n+1):
    if a[i]:
        ans[i]=0
    else:
        ans[i]=ans[i-1]+ans[i-2]
print(ans[n]%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
broken = []
for i in range(0, N+1):
	broken.append(False)
for i in range(0, M):
	broken[int(input())] = True
dp = [1, 1]
if broken[1]: dp[1] = 0
for i in range(2, N+1):
	if broken[i]: dp.append(0)
	else: dp.append(dp[-1]+dp[-2])
print(dp[N]%1000000007)

Submission status: Accepted

Solution code:


def main():
    num, koware_num = map(int, input().split())
    data = set([int(input()) for i in range(koware_num)])
    dp = [0 for i in range(num + 1)]
    dp[0] = 1
    if 1 not in data:
        dp[1] = 1

    mod = 10 ** 9 + 7

    for i in range(2, num + 1):
        if i in data:
            continue
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod

    print(dp[num])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
ans = 1
bro = list([])

for i in range(M):
    bro.append(int(input()))

bro.append(-1)

f = [0,0,1]

def Step (i):
    if i == bro[0]:
        bro.pop(0)
        f[0],f[1],f[2] = f[1],f[2],0
    else:
        f[0],f[1],f[2] = f[1],f[2],(f[1]+f[2])%(10**9+7)

for i in range(N):
    Step(i+1)

ans = f[2]%(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))
broken = set(broken)

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = (f2 + f1) % mod
  f2 = f1
  f1 = f
print(f)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
ans = 1
bro = list([])

for i in range(M):
    bro.append(int(input()))

bro.append(-1)

f = [0,0,1]

def Step (i):
    if i == bro[0]:
        bro.pop(0)
        f[0],f[1],f[2] = f[1],f[2],0
    else:
        f[0],f[1],f[2] = f[1],f[2],f[1]+f[2]

for i in range(N):
    Step(i+1)

ans = f[2]%(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * (num + 2)
    pattern[0] = 0
    for i in range(1, num + 2):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern

def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    if M > 0:
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N + 1]
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    # print("#", pattern)
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]
        else:
            total = (total * pattern[stepsList[k]]) % MOD
        # print("##", k, stepsList[k], pattern[stepsList[k]], total)

    return total


ans = solve()
print(ans)

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
mod = 10**9+7

a = [int(input()) for i in range(m)]

#dp[i]:i段目に来る場合の数
dp = [0]*(n+1)
dp[0]=1
for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    dp[i] += dp[i-1]
    if i >= 2:
      dp[i] += dp[i-2]
    dp[i] = dp[i]%mod
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mod = int(1e9+7)
f = [True for i in range(n+1)]
for i in range(m):
	f[int(input())] = False
dp=[1]+[0 for i in range(n+1)]
for i in range(n):
	if f[i+1]:
		dp[i+1] = (dp[i]+dp[i-1])%mod
print(dp[n])

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    a=set(a)
    dp[0]=1
    mod=10**9+7
#    dp[1]=dp[0]%mod
    for i in range(1,n+1):
        if i in a:
            continue
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
#    print(dp)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N , M = map(int,input().split())

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N+1) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
o = set(int(input()) for _ in range(m))
#print(o)
mod = (10**9)+7
dp = [0]*(n+1)
dp[0] = 1

for i in range(1,n+1):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  if i in o:
    dp[i] = 0
  #print(i,dp)
#print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

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

    ai = 0
    for i in range(N):
        if ai < M and A[ai] == i+1:
            dp[i+1] = 0
            ai += 1
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]

    ans = typical_stairs(N, M, A)
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int, input().split())
    stairs = [1]*(n+1)
    mod = 1000000007
    for _ in range(m):
        stairs[int(input())] = 0
    for i in range(2, n+1):
        stairs[i] = (stairs[i-2] + stairs[i-1]) * stairs[i]
    print(stairs[n] % mod)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect


def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

    A.sort()
    A.append(float('inf'))

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

    for i in range(N):
        if A[bisect.bisect_left(A, i+1)] == i+1:
            dp[i+1] = 0
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]

    ans = typical_stairs(N, M, A)
    print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[-1]*(n+1)
for i in range(m):
    idx=int(input())
    l[idx]=0
mod=10**9+7
if n!=1:
    if l[1]==-1:
        if l[2]==-1:
            l[1]=1;l[2]=2
        else:
            l[1]==1
    else:
        if l[2]==-1:
            l[2]=1
    if n>2:
        for i in range(3,n+1):
            if l[i]==-1:
                l[i]=(l[i-1]+l[i-2])%mod
            else:
                continue
    print(l[-1])
else:
    if l[1]==-1:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools

mod  = 1000000007

N, M=map(int, input().split())

broken = [0 for _ in range(N + 2)]

for i in range(M):
    n = int(input())
    broken[n] = True

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

print(dp[0])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
MOD = 10 ** 9 + 7

a = [int(input()) for _ in range(m)]

dp = [0] * (n+3)

for x in a:
    dp[x] = -1

dp[0] = 1

for i in range(n):
    if dp[i] == -1:
        continue
    if dp[i+1] != -1:
        dp[i+1] = ( dp[i+1] + dp[i] ) % MOD
    if dp[i+2] != -1:
        dp[i+2] = ( dp[i+2] + dp[i] ) % MOD

#print(dp)

print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

lst = [0] + [1] + [-1]*N
for i in range(M):
    lst[int(input())+1] = 0

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

print (lst[N+1]%1000000007)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

DP = [1] * (N+1)

for i in A:
    DP[i] = 0

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

print(DP[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import copy

sys.setrecursionlimit(1000000)

# input = sys.stdin.readline

# ~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~

MOD = 1000000007

N, M = map(int, input().split())
goods = [True] * (N + 4)
dp = [0] * (N + 4)

for _ in range(M):
    x = int(input())
    goods[x] = False

dp[0] = 1
for i in range(N + 1):
    if goods[i]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD


print(dp[N])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
dp[1] = int(1 not in a)
for i in range(2,n+1):
  if i in a:
    continue
  dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())

aa=[0 for i in range(100000+10)]
for i in range(m):
  a=int(input())
  aa[a]=1
#print(aa)

d=[0 for i in range(100000+10)]
p=1000000007

d[0]=1
if aa[1] == 0:
    d[1]=1
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    

print(d[n]%p)

Submission status: Accepted

Solution code:
def mulmod(x,y,p):
    return x*y % p

def test(n):
    if n<1:
        return 1
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = (memo[i-1] + memo[i-2])%1000000007
    return memo[n]

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)

for i in a:
    result = mulmod(test(i-pos-1),result,1000000007)
    pos = i+1
 
result = mulmod(test(n-pos),result,1000000007)
print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
#n=100
#a=[1, 23, 45, 67, 89]
aa=[0 for i in range(100000+10)]

for i in a:
    aa[i]=1
#print(aa)

d[0]=1
if aa[1] == 0:
    d[1]=1
else:
    d[1]=0
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0
#print(d)

print(d[n]%p)

Submission status: Accepted

Solution code:
c_mod=1000000007
n,m = map(int,input().split())
 
a_list=[]
for i in range(m):
    a_list.append(int(input()))

fib=[0]*(n+1)
fib[0]=1
fib[1]=1
for i in range(2,n+1):
    fib[i]=fib[i-1]+fib[i-2]

def count(s,e):
    return fib[e-s]
 
c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    # 各部分の移動方法
    end=a-1
    ans=ans*count(start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,end)%c_mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [0] * (N + 1)
    for _ in range(M):
        A[int(input())] = 1
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if A[i] == 1:
            continue
        dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [0] * (N + 2)
    for _ in range(M):
        A[int(input())] = 1
    dp = [0] * (N + 2)
    dp[-2] = 1
    for i in range(N - 1, -1, -1):
        if A[i] == 1:
            continue
        dp[i] = dp[i + 1] + dp[i + 2]
    print(dp[0] % 1000000007)


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = 0
S = [True]*(N+1)
for _ in range(M):
  a = int(input())
  S[a] = False
T = [0]*(N+1)
T[0] = 1
T[1] = 1 if S[1] else 0
for i in range(2, N+1):
  if S[i]:
    T[i] = int((T[i-1]+T[i-2])%1000000007)
print(T[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [True]*(N+1)
for _ in range(M):
  a = int(input())
  S[a] = False
T = [0]*(N+1)
T[0] = 1
T[1] = 1 if S[1] else 0
for i in range(2, N+1):
  if S[i]:
    T[i] = (T[i-1]+T[i-2])%1000000007
print(T[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=1000000007
f=[True for i in range(0,n)]
for i in range(m):
	f[int(input())]=False
dp=[1]+[0 for i in range(0,n+1)]
for i in range(0,n):
	if f[i]:
		dp[i+1] += dp[i]
		dp[i+1] %= mod
		dp[i+2] += dp[i]
		dp[i+2] %= mod
print(dp[n])

Submission status: Accepted

Solution code:
MOD = 1000000007

n , m = map(int,input().split())

a = [0 for i in range(n+1)]
for i in range(m):
    a[int(input())] = 1

count = [0 for i in range(n+1)]
for i in range(1,n+1):
    if a[i] == 1:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

mod = 10**9 + 7

li = [0]*(N+2)
li[0] = 0
li[1] = 1
for i in range(M):
    a = int(input())+1
    li[a] = -1

for i in range(2, N+2):
    if li[i] == -1:
        li[i] = 0
    else:
        li[i] = (li[i-1] + li[i-2]) % mod

print(li[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
def fib(n) :
    a, b = 1, 1
    if n==0 :
        return a
    elif n==1 :
        return b
    else :
        for i in range(n-1):
            a, b = b, a+b
        return b
a=[]
b=1

for i in range(M):
    a.append(int(input()))
    if a[i]-a[i-1] == 1 :
        b=0

def rest(num) :
    return num % 1000000007
c=0
if b==0 :
    print(c)
else :
    for i in range(M+1):
        if i == 0 == M :
            c += rest(fib(N))
        elif i == 0:
            c += rest(fib(a[i]-1))
        elif i == M:
            c = rest(c * fib(N-a[i-1]-1))
        else :
            c = rest(c * fib(a[i]-a[i-1]-2))
    print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*(n+1)
dp=[0]*(n+1)
mo=10**9+7
for i in range(m):
    a[int(input())]=-1
    
for i in range(n+1):
    if i==0:
        dp[i]=1
    elif i==1:
        if a[1]!=-1:
            dp[i]=1
    elif a[i]!=-1:
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]%=mo
print(dp[n]%mo)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, m = map(int, input().split())
dp = [0] * (n+1)
dp[0] = 1

# skip用 list
A = [0] * (n+1) 
for _ in range(m):
  broken = int(input())
  A[broken] = 1

# dp
for i in range(1, n+1):
  if A[i] == 1:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
#a = [0 for _ in range(N + 1)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(N + 2)]
A[0] = 0
A[1] = 1
for i in range(M):
    a = int(input()) + 1
    A[a] = -1
for i in range(2, N+2):
    if A[i] ==  -1:
        A[i] = 0
    else:
        A[i] = A[i-1]+ A[i-2]
        A[i] = A[i] % 1000000007
    #print(A)
print(A[N + 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n, m = intinput()
a = {int(sys.stdin.readline()) for _ in range(m)}
memo = [0 for x in range(n + 4)]
memo[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
    if i + 1 not in a:
        memo[i + 1] = (memo[i + 1] + memo[i]) % mod
    if i + 2 not in a:
        memo[i + 2] = (memo[i + 2] + memo[i]) % mod
print(memo[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=set()
dp=[0]*(n+1)
mo=10**9+7
for i in range(m):
    a.add(int(input()))

for i in range(n+1):
    if i==0:
        dp[i]=1
    elif i==1:
        if 1 not in a:
            dp[i]=1
    elif i not in a:
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]%=mo
        

print(dp[n]%mo)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [1 for _ in range(N)]

# 初期化する
for b in broken_stairs:
    dp[b] = 0

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(dp[-1])

Submission status: Accepted

Solution code:
n, m = list(map(int,input().split()))
a = []
for i in range(m):
  a.append(int(input()))
c = [0] * (n+2) #combination
for i in a:
  c[i] = -1
c[0] = 1

for i in range(n):
    if c[i] < 0:
      continue
    if c[i+1] >= 0:
        c[i+1] = c[i] + c[i+1]
    if c[i+2] >= 0:
        c[i+2] = c[i] + c[i+2]
    c[i] = c[i] % 10**9+7
print(c[n]%(10**9+7))

Submission status: Accepted

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Accepted

Solution code:
import math
 
N, M = map(int, input().split())
broken_a = [0] * (N + 1)
for _ in range(M):
  broken_a[int(input())] = 1

dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
  if broken_a[i]:
    dp[i] = 0
    continue
  if i == 1:
    dp[i] = dp[i - 1] % 1000000007
  else:
  	dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

Submission status: Accepted

Solution code:
lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))

nums = set(range(N)) - set(skip)

steps = [0] * (N + 2)
steps[0] = 1

for i in nums:
    steps[i+1] = (steps[i+1] + steps[i]) % P
    steps[i+2] = (steps[i+2] + steps[i]) % P

print steps[N]

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
D=[1] * (n+1)
for _ in range(m):
    D[int(input())] = 0
for i in range(2, n+1):
    D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

# 穴が開いている段
a = [int(input()) for _ in range(M)]

# 動的計画法
DP = [1] * (N + 1)

# 穴が開いている段への進み方は0通りにする
for idx in a:
    DP[idx] = 0

# 以下、漸化式のように解く
if N >= 2:
    for i in range(2, N+1):
        if DP[i] != 0:
            if DP[i - 1] != 0:
                if DP[i - 2] != 0:
                    DP[i] = DP[i - 1] + DP[i - 2]
                else:
                    DP[i] = DP[i - 1]
            else:
                if DP[i - 2] != 0:
                    DP[i] = DP[i - 2]
                else:
                    DP[i] = 0

print(DP[N]%MOD)

Submission status: Accepted

Solution code:
def fib(n):
    if n == 0: 
        return 0

    if n == 1: 
        return 1

    def matmul(M1, M2):
        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        return [[a11, a12], [a21, a22]]

    def matPower(mat, p):
        if p == 1: 
            return mat

        m2 = matPower(mat, p//2)
        if p % 2 == 0:
            return matmul(m2, m2)
        else: 
            return matmul(matmul(m2, m2),mat)

    Q = [[1,1],[1,0]]

    q_final = matPower(Q, n-1)
    return q_final[0][0]

N, M = map(int, input().split())
if(M==0):
    print(fib(N+1)%1000000007)
else:
    V = []
    for x in range(M):
        V.append(int(input()))

    result = 1

    for i in range(1, M):
        if(V[i]-V[i-1]==1):
            result = 0

    result *= fib(V[0])

    for x in range(1, M):
        result *= fib(V[x]-V[x-1]-1)

    if(V[M-1]!=N):
        result *= fib(N-V[M-1])

    print(result%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
DP = [1] * (N + 1)
for idx in a:
    DP[idx] = 0

if N >= 2:
    for i in range(2, N+1):
        if DP[i] != 0:
            if DP[i - 1] != 0:
                if DP[i - 2] != 0:
                    DP[i] = DP[i - 1] + DP[i - 2]
                else:
                    DP[i] = DP[i - 1]
            else:
                if DP[i - 2] != 0:
                    DP[i] = DP[i - 2]
                else:
                    DP[i] = 0

print(DP[N]%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
m = 10**9+7

dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in a:
  dp[1] = 0

for i in range(2, n+1):
  dp[i] = 0 if i in a else (dp[i-2] + dp[i-1]) % m

print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AL = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
amidx = 0
for i in range(1, N+1):
    if amidx < len(AL) and i == AL[amidx]:
        dp[i] = 0
        amidx += 1
    else:
        if i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i-1] + dp[i-2]
res = dp[-1] % (10**9+7)
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]

dev = 1000000007
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1

fall = [1 for _ in range(N+1)]

for i in range(M):
    fall[a[i]] = 0

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1]*(n+1)
for _ in range(m): D[int(input())]=0
for i in range(n+1):
    if i>1: D[i]=(D[i-1]+D[i-2])%(10**9+7)*D[i]
print(D[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i > 1:
        D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[i])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1]*(n+1)
for _ in range(m): D[int(input())]=0
for i in range(n+1):
    if i>1: D[i]=(D[i-1]+D[i-2])%(10**9+7)*D[i]
print(D[i])

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
dp = [1]*(n+1)
a = []
for i in range(m):
    ai = int(input())
    a.append(ai)

for i in a:
    dp[i] = 0

for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[n])

Submission status: Accepted

Solution code:
# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    #print(a)
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i < 2:
        continue
    D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[i])

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
dp = [0]*(n+2)
for i in a:
    dp[i] = -1
dp[0] = 1

for i in range(n):
    if dp[i]<0:
        continue
    dp[i] %= 10**9+7
    if dp[i+1]>=0:
        dp[i+1] += dp[i]
    if dp[i+2]>=0:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i < 2 or D[i] == 0:
        continue
    D[i] = (D[i-1] + D[i-2]) % 1000000007 
print(D[i])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if D[i] == 0 or i < 2:
        continue
    D[i] = (D[i-1] + D[i-2]) % 1000000007 
print(D[i])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7

s = [True for _ in range(n+1)]
for _ in range(m):
    s[int(input())] = False

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

for now in range(n+1):
    for nxt in range(now+1, min(n+1, now+3)):
        if s[nxt]:
            dp[nxt] += dp[now]
            dp[nxt] %= mod

print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

mod = 1000000007
 
N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]
 
for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()
 
memo = {0: 1, 1: 1, 2: 2, 3: 3}
 
def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
 
ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod
 
    lo = a + 1
    pre = a
 
print(ans)