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:
n,m = map(int,input().split())
cnt=[]
l=[int(input()) for _ in range(m)]
for i in range(n+1):
    cnt.append(-1)
for i in range(m):
    cnt[l[i]]=0
cnt[0]=1
for i in range(1,n+1):
    if cnt[i]==0:
        continue
    else:
        cnt[i]=cnt[i-1]
        if i>1:
            cnt[i]+=cnt[i-2]
#print(cnt)
print(cnt[n]%1000000007)

Submission status: Accepted

Solution code:
mod=10**9+7
n,m=map(int,input().split())
a=[int(input())for _ in range(m)]
a.append(n+1)
fib=[1,1]
for i in range(n):
	r=fib[-1]+fib[-2]
	fib.append(r%mod)
ans=1
now=0
for x in a:
	ans*=fib[x-1-now]
	if x-1-now<0:
		print(0)
		exit()
	ans%=mod
	now=x+1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = set([int(input()) for i in range(m)])
mod = 10**9+7

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
st = [1 for _ in range(N+1)]
for _ in range(M):
    st[int(input())] = 0
dp = [0 for _ in range(N+1)]
MOD = int(1e9) + 7
dp[0] = 1
# DP
if st[1]:
    dp[1] = 1
for i in range(2, N+1):
    if st[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[-1])

Submission status: Accepted

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

stair = [True] * N
for i in a:
    stair[i-1] = False

# DP
dp = [0] * N
if stair[0]:
    dp[0] = 1
if N >= 2:
    if stair[1]:
        dp[1] = dp[0] + 1
    else:
        dp[1] = 0

for i in range(2, N):
    if not stair[i]:
        dp[i] = 0
        continue
    if stair[i-1] and stair[i-2]:
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    elif stair[i-1]:
        dp[i] = dp[i-1]
    elif stair[i-2]:
        dp[i] = dp[i-2]

print(dp[N-1])

Submission status: Accepted

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

Flag = [True for _ in range(N+1)]
for a in A:
    Flag[a] = False

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

Dp[0] = 1
if 1 not in A:
    Dp[1] = 1
for i in range(N-1):
    if Flag[i+2]:
        Dp[i+2] = (Dp[i] + Dp[i+1])%(10**9+7)
print(Dp[-1])

Submission status: Accepted

Solution code:
#mod = 10**9 + 7
#n, m = map(int, input().split())
#a = []
#for _ in range(m):
#    x = int(input())
#    if len(a) > 0 and x == a[-1] + 1:
#        print(0)
#        exit()
#    a.append(x)
#j = 0
#dp = [0] * (n+1)
#dp[0] = 1
#for i in range(n):
#    if j < m and i >= a[j]:
#        j += 1
#    if j < m and i+1 == a[j]:
#        pass
#    else:
#        dp[i+1] += dp[i]
#        dp[i+1] %= mod
#    if j < m and i+2 == a[j]:
#        pass
#    elif i+2 <= n:
#        dp[i+2] += dp[i]
#        dp[i+2] %= mod
#print(dp[-1])
mod = 10**9 + 7
n, m = map(int, input().split())
ok = [True]*(n+1)
for _ in range(m):
    a = int(input())
    ok[a] = False
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if ok[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 <= n and ok[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n, m = map(int, input().split())
a = []
for _ in range(m):
    x = int(input())
    if len(a) > 0 and x == a[-1] + 1:
        print(0)
        exit()
    a.append(x)
j = 0
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if j < m and i >= a[j]:
        j += 1
    if j < m and i+1 == a[j]:
        pass
    else:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if j < m and i+2 == a[j]:
        pass
    elif i+2 <= n:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

print(dp[n]%mod)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

nums = [0]*(n+1)
nums[0]  =1
if 1 not in a: nums[1] = 1

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
stairs = [1]*(n+1)
for _ in range(m):
  stairs[int(input())] = -1

flg = False
for i in range(2,n+1):
  if stairs[i]==-1:
    pass
  elif stairs[i-1]==-1 and stairs[i-2]==-1:
    flg=True
    break
  elif stairs[i-1]==-1:
    stairs[i] = stairs[i-2]
  elif stairs[i-2]==-1:
    stairs[i] = stairs[i-1]
  else:
    stairs[i] = stairs[i-1] + stairs[i-2]
if flg:
  print(0)
else:
  print(stairs[-1]%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[1]*(n+1)
flg=0
for i in range(m):
  a[int(input())]=-1
for i in range(2,n+1):
  if a[i]==-1:
    pass
  elif a[i-1]==-1 and a[i-2]==-1:
    flg=1
    break
  elif a[i-1]==-1:
    a[i]=a[i-2]
  elif a[i-2]==-1:
    a[i]=a[i-1]
  else:
    a[i]=a[i-1]+a[i-2]
if flg==1:
  print(0)
else:
  print(a[-1]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
broken = [0] * (n + 1)

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denger = [False] * (n + 1)
for i in range(m):
    denger[int(input())] = True

DP = [0] * (n + 1)
DP[0] = 1
for i in range(n):
    if not denger[i + 1]:
        DP[i + 1] += DP[i]
    if i + 2 <= n and not denger[i + 2]:
        DP[i + 2] += DP[i]

print(DP[-1] % 1000000007)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
B=[1]+[1]+[0]*(N-1)
for j in range(M):
    a=int(input())
    B[a]=-1
    if a==1:
        B[a]=0
i=2
while i<=N:
    if B[i]==-1:
        B[i]=0
    else:
        B[i] = (B[i - 1] + B[i - 2]) % (10 ** 9 + 7)
    i+=1
print(B[N])

Submission status: Accepted

Solution code:
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
n, m = map(int, input().split())
broken = []
for i in range(m):
  broken.append(int(input()))
L = -1
intv = []
for i in broken:
  intv.append(i - L - 2)
  L = i
intv.append(n - L - 1)
res = 1
#print(intv)
if -1 in intv[1:]:
  print(0)
  exit()
dv = 10 ** 9 + 7
for i in intv:
  res *= Fib(i + 2)
  res %= dv
print(res)

Submission status: Accepted

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

route=[0]*3+[0]*max(0,N-2)
for a in A:
    route[a]=-1

if route[1]!=-1:
    route[1]=1
else:
    route[1]=0

if route[2]!=-1:
    route[2]=1+route[1]
else:
    route[2]=0

i=3
while i<=N:
    if route[i]==-1:
        route[i]=0
    else:
        route[i]=(route[i-1]+route[i-2])%1000000007
    i+=1

print(route[N])

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
mod = 1000000007

if n == 1:
    print(1)
    sys.exit()

B = ['.'] * (n + 1)
for a in A:
    B[a] = '#'
    
dp = [0] * (n + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, n + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [0]*m
#for i in range(m):
 # a[i] = int(input())
a = set([int(input()) for i in range(m)])
dp = [0]*(n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 2)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        if memo[i] == 0:
            count1 = rec(i - 1)
            count2 = rec(i - 2)
            memo[i] = (count1 + count2) % 1000000007
        return memo[i]
    return rec(N)


print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 2)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
        return memo[i]
    return rec(N)


print(solve())

Submission status: Accepted

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

dp = [0]*(N+1)
for j in a:
  dp[j]=-1

dp[0]=1
if dp[1] != -1:
  dp[1]=1
elif dp[1] == -1:
  dp[1]=0

for i in range(2,N+1):
  if dp[i] != -1:
    dp[i] = dp[i-1]+dp[i-2]
  elif dp[i] == -1:
    dp[i]=0

print(dp[N]%(10**9+7))

Submission status: Accepted

Solution code:
# DP(動的計画法)
N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))

m = 1000000007

t = [0] * (N + 2)
t[0] = 1
for i in range(N):
    if i in A:
        t[i] = 0
    else:
        t[i + 1] = (t[i + 1] + t[i]) % m
        t[i + 2] = (t[i + 2] + t[i]) % m
print(t[N])

Submission status: Accepted

Solution code:
mod = 10**9 + 7
N, M = map(int, input().split())
state = [True]*(N+1)
ans = [0]*(N+1)
for _ in range(M):
    state[int(input())] = False

ans[0] = 1
for i in range(N):
    if state[i]:
        ans[i+1] += ans[i]
        if i < N-1:
            ans[i+2] += ans[i]
print(ans[-1]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
oks = [True]*(n+1)
for i in range(m):
    a = int(input())
    oks[a] = False

dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1,min(n,i+2)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= (10**9+7)
print(dp[n])

Submission status: Accepted

Solution code:
import sys

N, M = [int(n) for n in input().split()]

A = []

modulus = 10**9 + 7

for _ in range(M):
    a = int(input())
    if A and A[-1] + 1 == a:
        print(0)
        sys.exit(0)
    A.append(a)

fib_list = [1, 1]

def fib_mod(n):
    l = len(fib_list)
    if n < l:
        return fib_list[n]
    while l <= n:
        fib_list.append((fib_list[-1] + fib_list[-2]) % modulus)
        l += 1
    return fib_list[-1]

total = 1
left = 0

A.append(N+1)

for a in A:
    right = a - 1
    total *= (fib_mod(right - left) % modulus)
    left = right + 2


print(total % modulus)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [0]*(n+1)
for j in range(m):
    pos = int(input())
    a[pos] = 1

MOD = 10**9+7

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

for i in range(n+1):
    if a[i] == 1:
        step[i] = 0
    else:
        if i != 0 and i != 1:
            step[i] = (step[i-1] + step[i-2]) % MOD

print(step[-1])

Submission status: Accepted

Solution code:

n,m=[int(x) for x in input().rstrip().split()]
A=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0 for i in range(n+10)]
no=[True for i in range(n+10)]
for i in A:
  no[i]=False


if no[1]==True:
  dp[1]=1
dp[0]=1
for i in range(2,n+1):
  if no[i]==True:
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

MOD = 10**9+7

ok = set([i+1 for i in range(n)]) - set(a)
ok = list(ok)
ok.sort()

MAX_N = 10**5+5
dp = [0]*MAX_N

for i in ok:
    if i == 1:
        dp[i] = 1
    elif i == 2 and dp[1] == 0:
        dp[i] = 1
    elif i == 2:
        dp[i] = 2
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] %= MOD
        
print(dp[n])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
m=10**9+7
a.append(N+1)
def mul(a,b):
    c=[[0]*len(b[0])for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m
    return c
def pow(a,n):
    b=[[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i]=1
    while 0<n:
        if n&1==1:
            b=mul(a,b)
        a=mul(a,a)
        n=n>>1
    return b                
if M==0:
  A=[[1,1],[1,0]]
  print(pow(A,N+1)[1][0])
elif M==1:
  A=[[1,1],[1,0]]
  print((pow(A,a[0])[1][0]*pow(A,N-a[0])[1][0])%m)
else:
  ans=1
  for i in range(M+1):
    A=[[1,1],[1,0]]
    if a[i]+1==a[i-1]:
      ans=0
      break
    if i==0:
      if a[i]!=1:
        ans=ans*pow(A,a[0])[1][0]
        ans=ans%m
    elif i==M:
      ans=ans*pow(A,a[i]-a[i-1]-1)[1][0]
      ans=ans%m
    else:
      ans=ans*pow(A,a[i]-a[i-1]-1)[1][0]
      ans=ans%m
  print(ans)

Submission status: Accepted

Solution code:
#3問目
N, M = map(int, input().split())
A = set({})
MAX = 1000000007
for i in range(M):
    a = int(input())
    A.add(a)
dp = [0] * (N+1)
dp[0] = 1
if 1 in A:
    dp[1] = 0
else:
    dp[1] = 1
    
for i in range(2, N+1):
    if i in A:
        dp[i] = 0
    else:
        #あきがなかったら
        dp[i] = (dp[i-2] + dp[i-1])%MAX
print(dp[N])

Submission status: Accepted

Solution code:

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

oks = [True] * (N+1)
for _ in range(M):
    a = int(input())
    oks[a] = False

dp = [0] * (N+1)
dp[0] = 1
for now in range(N):
    for next in range(now+1, min(N, now+2)+1):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= MOD
            
print(dp[N])

Submission status: Accepted

Solution code:
N,A=map(int,input().split())
arr=[int(input()) for i in range(A)]

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


for i in range(A):
    dp[arr[i]]=-1

if dp[1]==-1:
    ans[1]=0

for i in range(2,N+1):
    if dp[i]!=-1:
        ans.append(ans[i-1]+ans[i-2])
    elif dp[i]==-1:
        ans.append(0)
    
print(ans[-1]%1000000007)

Submission status: Accepted

Solution code:
#n=int(input())
n,m=map(int,input().split())
#t=int(input())
#al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

dp=[0]*(n+1)
mod=10**9+7
broken={i:False for i in range(1,n+1)}
for i in range(m):
    a=int(input())
    broken[a]=True
if broken[1]:
    dp[1]=0
else:
    dp[1]=1
dp[0]=1
for i in range(2,n+1):
    if not broken[i]:
        dp[i]=(dp[i-1]+dp[i-2])%mod

print(dp[n])

Submission status: Accepted

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

l = [0]*(N+1)
l[0] = 1
j = 0
for i in range(1, N+1):
  if j < M and i == a[j]:
    j += 1
  else:
    if i == 1:
      l[1] = 1
    else:
      l[i] = (l[i-1] + l[i-2]) % (10**9+7)

print(l[N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():

    N, M, *A = map(int, read().split())
    B = [False] * (N + 1)
    for a in A:
        B[a] = True

    dp = [0] * (N + 10)
    dp[0] = 1
    for i in range(N):
        if B[i]:
            continue
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
        dp[i + 2] = (dp[i + 2] + dp[i]) % MOD

    print(dp[N])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
TF = [True]*(N+1)
for m in range(M):
  TF[int(input())] = False
dp = [0]*(N+1)
dp[0]=1
for n in range(N):
  if TF[n] and n<N:
    dp[n+1]+=dp[n]
  if TF[n] and n<N-1:
    dp[n+2]+=dp[n]
print(dp[N]%1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    a = set(a)
    dp = [0] * (N+2)
    dp[0] = 1
    for i in range(N):
        if i in a:
            dp[i] = 0
        dp[i+1] = (dp[i+1] + dp[i]) % MOD
        dp[i+2] = (dp[i+2] + dp[i]) % MOD
    return dp[N]


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, a))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#動的計画法(DP)
#ブログ「けんちょんの競プロ精進記録」参考
#URL: https://drken1215.hatenablog.com/entry/2019/06/10/140000


N,M = map(int,input().split())
MOD = 1000000007
issafe = [True]*(N+1) # issafe[v]: v段目が壊れていないかどうか

for _ in range(M):
    i = int(input())
    issafe[i] = False # i 段目は壊れている

#DPテーブル
dp = [0]*(N+1)

#初期条件
dp[0] = 1
if issafe[1]:dp[1] = 1

#ループ
for n in range(2,N+1):
    if issafe[n-1]: dp[n] += dp[n-1]
    if issafe[n-2]: dp[n] += dp[n-2]
    dp[n] %= MOD

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n, m =map(int,input().split())
lis={0:1,1:1}
for _ in range(m):
  lis[int(input())]=0 
def saiki(x):
  if x not in lis:
        d=saiki(x-1)+saiki(x-2)
        if d >10**9+7:
          lis[x]= d % (10**9+7)
          return lis[x]
        else:
          lis[x]=d
          return d
  else:
    return lis[x]
      
print(saiki(n))

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
解説AC
解法：基本的な動的計画法(DP)
'''
import itertools


def myAnswer(N:int,M:int,A:list) -> int:
   safe_stairs =[True] * (N + 1)
   mod = 10**9 + 7
   for a in A:
      safe_stairs[a] = False

   DP = [0] * (N+1)
   DP[0] = 1
   if safe_stairs[1]:DP[1] = 1

   for n in range(2,N + 1):
      if safe_stairs[n - 1]:
         DP[n] += DP[n - 1]
      if safe_stairs[n - 2]:
         DP[n] += DP[n - 2]
      DP[n] %= mod

   return DP[N]
      



def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = [int(input()) for _ in range(M)]
   print(myAnswer(N,M,A))

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''
import itertools


def myAnswer(N:int,M:int,A:list) -> int:
   safe_stairs =[True] * (N + 1)
   mod = 10**9 + 7
   for a in A:
      safe_stairs[a] = False

   DP = [0] * (N+1)
   DP[0] = 1
   if safe_stairs[1]:DP[1] = 1

   for n in range(2,N + 1):
      if safe_stairs[n - 1]:
         DP[n] += DP[n - 1]
      if safe_stairs[n - 2]:
         DP[n] += DP[n - 2]
      DP[n] %= mod

   return DP[N]
      



def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = [int(input()) for _ in range(M)]
   print(myAnswer(N,M,A))

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mod = 1000000007
a = set(int(input()) for _ in range(m))

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i not in a: dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N, M = MI()
mod = 10**9 + 7
stairs = [1] + [0] * N
safe = [True] * (N + 1)

for _ in range(M):
    a = int(input())
    safe[a] = False

if safe[1]:
    stairs[1] = 1

for i in range(2, N + 1):
    if not safe[i - 1] and not safe[i - 2]:
        print(0)
        sys.exit()
        
    if safe[i - 1]:
        stairs[i] += stairs[i - 1]
    
    if safe[i - 2]:
        stairs[i] += stairs[i - 2]
    
    stairs[i] %= mod

print(stairs[N])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib[n-1]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9+7

dp = [0] * (10**5 + 3)
dp[1] = 0
dp[2] = 1
dp[3] = 2
for i in range(3, len(dp)):
    dp[i] = dp[i-1] + dp[i-2] 

res = 1
bef = -1
if M > 0:
    for a in a_list:
        res *= dp[a-bef]
        res %= MOD
        bef = a
res *= dp[N-bef+1]
res %= MOD

print(res)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    As = set([int(input()) for _ in range(m)])
    mod = 1000000007

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1

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

    ans = dp[n] % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 7
N, M = list(map(int,input().split()))
A = [1 for _ in range(N + 1)]
for i in range(M):  A[int(input())] = 0
dp = [0 for _ in range(N + 1)]
dp[0] = 1
for i in range(1, N + 1):
    if A[i] == 1:  dp[i] = (dp[i - 1] + dp[i - 2]) % INF
print(dp[N] % INF)

Submission status: Accepted

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

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

mod = 1000000007
nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1
for i in range(2,n+1):
  if i in a: continue
  nums[i] = nums[i-1] + nums[i-2]

print(nums[n]%mod)

Submission status: Accepted

Solution code:
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n] % 1000000007 if DP[n] != 0 else 0)

Submission status: Accepted

Solution code:
MOD = 1000000007
# f(x) = f(x - 1) + f(x - 2)の場合のdp
def f_dp(x, a):
    dp = [0] * (x + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, x + 1):
        if i not in a:
            dp[i] = dp[i - 1] + dp[i -2]
    return dp[n] % MOD

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])

    dp = f_dp(n, a)
    print(dp)

Submission status: Accepted

Solution code:
MOD = 10**9+7


def solve(n, m, ax):
    bx = []

    for i in range(n):
        is_broken = ax[i]
        if i == 0:
            if is_broken == 1:
                bx.append(0)
            else:
                bx.append(1)
        elif i == 1:
            if is_broken == 1:
                bx.append(0)
            else:
                bx.append(bx[0]+1)
        elif is_broken == 1:
            bx.append(0)
        else:
            if ax[i-2] == 1 and ax[i-1] == 1:
                bx.append(0)
            elif ax[i-2] == 1 and ax[i-1] == 0:
                bx.append(bx[i-1])
            elif ax[i-2] == 0 and ax[i-1] == 1:
                bx.append(bx[i-2])
            else:
                bx.append(bx[i-2] + bx[i-1])


    return bx[-1] % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    ax = [0]*(n)
    for i in range(m):
        ax[int(input())-1] += 1

    print(solve(n, m, ax))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) # ここが'list'だとPypyでも通らない

def ptn_num(x): # 'x'stepまでのパターン数
    dp = [0] * (x+1) # DP枠_including step'0'
    if 1 in broken: # 固定部分_in case, step'1' broken 
        dp[:2] = 1, 0
    else:
        dp[:2] = 1, 1 # 固定部分_Usually

    for i in range(2, x+1):
        if i not in broken: # 階段が壊れてない場合...
            dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) # -1段目と-2段目の合計
    print(dp[-1])

ptn_num(n)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) # ここが'list'だとPypyでも通らない

def ptn_num(x): # 'x'stepまでのパターン数
    dp = [0] * (x+1) # DP枠_including step'0'
    if 1 in broken: # in case, step'1' broken 
        dp[:2] = 1, 0
    else:
        dp[:2] = 1, 1 # Usually

    for i in range(2, x+1):
        if i not in broken: # 階段が壊れてない場合...
            dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) # -1段目と-2段目の合計
    print(dp[-1])

ptn_num(n)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = set(map(int, [input() for _ in range(m)]))

dp = [0] * (n+1)
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

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

print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = set(map(int, [input() for _ in range(m)]))

dp = [0] * (n+1)
# 0段目と1段目は1通り（但し、１段目が壊れていない場合）（0 段目は「なにもしない」という から1 通り）
dp[:2] = 1, 1 if 1 not in a else 0 

for i in range(2, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2])

print(dp[-1] % (10**9+7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) # ここが'list'だとPypyでも通らない

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0 # 連続して壊れている階段を記録, '2'でゴール不可能
        if 1 in broken: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken: # 階段が壊れている場合は...
                cnt += 1 # 壊れている階段を記録するのみ
                if cnt == 2: # 2段連続で壊れている場合
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7) # -1段目と-2段目の合計
                cnt = 0 # 壊れている階段の記録はリセット
        print(dp[-1])

ptn_num(n)