Problem:


Score: 400 points

Problem Statement

Amidakuji is a traditional method of lottery in Japan.

To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.

A valid amidakuji is an amidakuji that satisfies the following conditions:

No two horizontal lines share an endpoint.

The two endpoints of each horizontal lines must be at the same height.

A horizontal line must connect adjacent vertical lines.

Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.

For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.

Constraints

H is an integer between 1 and 100 (inclusive).

W is an integer between 1 and 8 (inclusive).

K is an integer between 1 and W (inclusive).

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

1 3 2

Sample Output 1

1

Only the following one amidakuji satisfies the condition:

Sample Input 2

1 3 1

Sample Output 2

2

Only the following two amidakuji satisfy the condition:

Sample Input 3

2 3 3

Sample Output 3

1

Only the following one amidakuji satisfies the condition:

Sample Input 4

2 3 1

Sample Output 4

5

Only the following five amidakuji satisfy the condition:

Sample Input 5

7 1 1

Sample Output 5

1

As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.

Sample Input 6

15 8 5

Sample Output 6

437760187

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



Sample input:
1 3 2


Sample output:
1

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 10**9 + 7

dp = [0]*W
dp[0] = 1

OK = [0, 1, 1, 2, 3, 5, 8, 13]
NG = [0, 1, 2, 3, 5, 8, 13, 21]

if W == 1:
  print(dp[K-1])
else:
  for _ in range(H):
    temp = dp[:]
    for i in range(W):
      if i == 0:
        dp[i] = temp[i] * NG[W-1-i] + temp[i+1] * OK[W-1-i]
      elif i == W-1:
        dp[i] = temp[i-1] * OK[i] + temp[i] * NG[i]
      else:  
        dp[i] = temp[i-1] * OK[i] * NG[W-1-i] + temp[i] * NG[i] * NG[W-1-i] + temp[i+1] * NG[i] * OK[W-1-i]
      dp[i] %= mod
  print(dp[K-1])

Submission status: Accepted

Solution code:
import sys
from itertools import product

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


def main():
    H, W, K = map(int, readline().split())

    A = product((0, 1), repeat=W - 1)
    B = []
    for bars in A:
        ok = True
        for i in range(W - 2):
            if bars[i] and bars[i + 1]:
                ok = False
                break
        if ok:
            B.append(bars)

    dp = [0] * W
    dp[0] = 1

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for bars in B:
            for i in range(W):
                if i > 0 and bars[i - 1]:
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and bars[i]:
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print(dp[K - 1])

    return


if __name__ == '__main__':
    main()

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():
    H, W, K = map(int, readline().split())

    dp = [0] * W
    dp[0] = 1

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for mask in range(1 << (W - 1)):
            ok = True
            for i in range(W - 2):
                if mask & (1 << i) and mask & (1 << (i + 1)):
                    ok = False
                    break
            if not ok:
                continue
            for i in range(W):
                if i > 0 and mask & (1 << (i - 1)):
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and mask & (1 << i):
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print(dp[K - 1])

    return


if __name__ == '__main__':
    main()

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():
    H, W, K = map(int, readline().split())

    dp = [0] * W
    dp[0] = 1

    for _ in range(H):
        dp, dp_prev = [0] * W, dp
        for mask in range(1 << (W - 1)):
            ok = True
            for i in range(W - 2):
                if mask & (1 << i) and mask & (1 << (i + 1)):
                    ok = False
            if not ok:
                continue
            for i in range(W):
                if i > 0 and mask & (1 << (i - 1)):
                    dp[i - 1] = (dp[i - 1] + dp_prev[i]) % MOD
                elif i < W - 1 and mask & (1 << i):
                    dp[i + 1] = (dp[i + 1] + dp_prev[i]) % MOD
                else:
                    dp[i] = (dp[i] + dp_prev[i]) % MOD

    print(dp[K - 1])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w,k = map(int,ipt().split())
    nm = [1,1,2,3,5,8,13,21,34]
    dp = [0]*(w+2)
    dp[1] = 1
    for i in range(h):
        ndp = [0]*(w+2)
        for j in range(1,w+1):
            ndp[j] = dp[j]*nm[j-1]*nm[w-j]+dp[j-1]*nm[j-2]*nm[w-j]+dp[j+1]*nm[j-1]*nm[w-j-1]
            ndp[j] %= mod
        dp = ndp*1
#        print(dp)

    print(dp[k])


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, K = map(int, input().split())
    K -= 1
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            for bit in range(1 << (W - 1)):
                flg = True
                for mask in range(W - 2):
                    if (bit & (1 << mask)) and (bit & (1 << (mask + 1))):
                        flg = False
                if flg:
                    next_j = j
                    if bit & (1 << j):
                        next_j = j + 1
                    elif j > 0 and (bit & (1 << (j - 1))):
                        next_j = j - 1
                    dp[i + 1][next_j] = (dp[i + 1][next_j] + dp[i][j]) % mod
    print(dp[H][K])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w, k = ns()
    dp = [[0 for _ in range(w)] for __ in range(h + 1)]
    dp[0][0] = 1
    fibo = [1, 2]
    for i in range(10):
        fibo.append(fibo[-1] + fibo[-2])

    for y in range(1, h + 1):
        for x in range(w):
            if x == 0:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    # from R
                    dp[y][x] += dp[y - 1][x + 1] * fibo[max(0, w - 1 - 2)]
            elif x == w - 1:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[max(0, w - 1 - 1)]
                if w > 1:
                    # from L
                    dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, w - 1 - 2)]
            else:
                # from U
                dp[y][x] += dp[y - 1][x] * fibo[x - 1] * fibo[max(0, w - 1 - x - 1)]
                # from L
                dp[y][x] += dp[y - 1][x - 1] * fibo[max(0, x - 1 - 1)] * fibo[max(0, w - 1 - x - 1)]
                # from R
                dp[y][x] += dp[y - 1][x + 1] * fibo[x - 1] * fibo[max(0, w - 1 - x - 2)]
            dp[y][x] %= MOD

    print(dp[h][k - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())

WW = [0]*(W+1)
WW[0] = 1
WW[1] = 1
for i in range(2, W+1):
    WW[i] = WW[i-1] + WW[i-2]
DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j+1]*WW[W-2]
        elif j == W-1:
            DP[i][j] = DP[i-1][j]*WW[W-1]
            if W > 1:
                DP[i][j] += DP[i-1][j-1]*WW[W-2]
        else:
            DP[i][j] = DP[i-1][j]*WW[j]*WW[W-1-j]+DP[i-1][j-1] * \
                WW[j-1]*WW[W-1-j]+DP[i-1][j+1]*WW[j]*WW[W-2-j]

        DP[i][j] %= mod
# print(DP, WW)
print(DP[-1][K-1])

Submission status: Accepted

Solution code:
from itertools import combinations

H,W,K=map(int,input().split())
dp=[[0 for i in range(W)] for j in range(H+1)]

mod=10**9+7

if W==1:
  if K==1:print(1)
  else:print(0)
  exit()

memo={}
def is_separate(c):
  for i in range(len(c)-1):
    if c[i+1]-c[i] == 1:
      return False
  return True

def n_select(occupied):
  if memo.get(occupied):
    return memo[occupied]
  else:
    count=1
    if len(occupied)==1:
      for r in range(1,W//2+1):
        for c in combinations(range(W-1),r=r):
          if occupied[0]-1 not in c and occupied[0] not in c:
            if is_separate(c):
              count += 1
    if len(occupied)==2:
      for r in range(1,W//2+1):
        for c in combinations(range(W-1),r=r):
          if occupied[0]-1 not in c and occupied[0] not in c and occupied[0]+1 not in c:
            if is_separate(c):count += 1
  memo[occupied] = count
  return count

dp[0][0]=1
for i in range(1,H+1):
  for j in range(W):
    if j==0:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j+1]*n_select((j,j+1))
    elif j==W-1:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j-1]*n_select((j-1,j))
    else:
      dp[i][j] = dp[i-1][j]*n_select((j,))+dp[i-1][j+1]*n_select((j,j+1))+dp[i-1][j-1]*n_select((j-1,j))

print(dp[-1][K-1] % mod)

Submission status: Accepted

Solution code:
def f(i):
  if i == W-1:
    for j in range(W-2):
      if s[j] == s[j+1] == 1:
        return
    global x
    for j in range(W):
      if j == 0:
        if s[0] == 1:
          x[0][1] += 1
        else:
          x[0][0] += 1
      elif j == W - 1:
        if s[W-2] == 1:
          x[W-1][W-2] += 1
        else:
          x[W-1][W-1] += 1
      else:
        if s[j-1] == 1:
          x[j][j-1] += 1
        elif s[j] == 1:
          x[j][j+1] += 1
        else:
          x[j][j] += 1 
    return
  s[i] = 1
  f(i + 1)
  s[i] = 0
  f(i + 1)

H,W,K=map(int, input().split())
MOD = pow(10, 9) + 7
s = [0] * (W - 1)
x = [[0] * W for _ in range(W)]
if not W == 1:
  f(0)
else:
  print(1)
  exit()
dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for j in range(W):
    for l in range(W):
      dp[i][j]+=dp[i-1][l]*x[l][j]
      dp[i][j]%=MOD
print(dp[H][K-1])

Submission status: Accepted

Solution code:
H,W,K = list(map(int,input().split()))

goal = [0 for i in range(W)]
goal[0] = 1
oldGoal = [0 for i in range(W)]
oldGoal[0] = 1
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

if W == 1:
    print(1)
    exit()

for i in range(H):
    for j in range(W):
        if j == 0:
            a1 = oldGoal[j] * fib[W-1]
            a2 = oldGoal[j+1] * fib[W-2]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            goal[j] = a1 + a2
        elif j == W - 1:
            a1 = oldGoal[j-1] * fib[W-2]
            a2 = oldGoal[j] * fib[W-1]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            goal[j] = a1 + a2
        else:
            a1 = oldGoal[j-1] * fib[j-1] * fib[W-j-1]
            a2 = oldGoal[j] * fib[j] * fib[W-j-1]
            a3 = oldGoal[j+1] * fib[j] * fib[W-j-2]
            a1 = a1 % 1000000007
            a2 = a2 % 1000000007
            a3 = a3 % 1000000007
            goal[j] = a1 + a2 + a3
    for k in range(W):
        oldGoal[k] = goal[k]
print(goal[K-1] % 1000000007)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
if W==1:
  print(1)
  exit()
  
import itertools
A=list(itertools.product([0,1], repeat=W-1))

B=[]
for i in A:
  x=0
  for j in range(W-2):
    if i[j]==1 and i[j+1]==1:
      x=1
  if x==0:
    B.append(i)

D=[[0,0,0] for i in range(W)]
for i in B:
  for j in range(W-1):
    if i[j]==1:
      D[j+1][0]+=1
      D[j][2]+=1
    if j==0 and i[j]==0:
      D[j][1]+=1
    if j==W-2 and i[j]==0:
      D[j+1][1]+=1
    if j<W-2:
      if i[j]==0 and i[j+1]==0:      
        D[j+1][1]+=1
dp=[[0]*W for i in range(H+1)]
mod=10**9+7
dp[0][0]=1
for i in range(H):
  for j in range(W):
    if j==0:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j+1]*D[j][2]
    elif j==W-1:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]
    else:
      dp[i+1][j]=dp[i][j]*D[j][1]+dp[i][j-1]*D[j][0]+dp[i][j+1]*D[j][2]
    dp[i+1][j]%=mod
print(dp[-1][K-1])

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
MOD = 10**9+7
memo = [[0]*(w+1) for _ in range(h+1)]
dp = [[1]*2 for _ in range(w+1)]
dp[0][0] = 0
for i in range(2, w+1):
    for j in range(2):
        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][0]
#print(dp)
def poss_of_ok_spaces(idx,straight):
    if straight:
        ok_spaces_l = max(idx - 1 - 1, 0)
        ok_spaces_r = max(w - idx - 1, 0)
        return sum(dp[ok_spaces_l])%MOD * sum(dp[ok_spaces_r])%MOD
    else:
        #右の数値を飛ばす前提
        ok_spaces_l = max(idx - 1 - 2, 0)
        ok_spaces_r = max(w - idx - 1, 0)
        return sum(dp[ok_spaces_l])%MOD * sum(dp[ok_spaces_r])%MOD

def rc(n,idx):
    if memo[n][idx] != 0:
        return memo[n][idx]
    if n == 1:
        if idx == k:
            return poss_of_ok_spaces(idx,True)%MOD
        elif k == idx + 1:
            return poss_of_ok_spaces(k,False)%MOD
        elif k == idx - 1:
            return poss_of_ok_spaces(idx,False)%MOD
        else:
            return 0
    ret = rc(n-1,idx)%MOD*poss_of_ok_spaces(idx,True)%MOD
    if idx + 1 <= w:
        ret += rc(n-1,idx+1)%MOD*poss_of_ok_spaces(idx+1,False)%MOD
    if idx - 1 >= 1:
        ret += rc(n-1,idx-1)%MOD*poss_of_ok_spaces(idx,False)%MOD
    ret %= MOD
    memo[n][idx] = ret
    return ret
print(rc(h,1))

Submission status: Accepted

Solution code:
h,w,k=list(map(int,input().split()))

dp=[[0]*(h+2) for _ in range(w+2)]
comb=[1]*(w+5)
comb[2]=2
for i in range(3,w+1):
    for j in range(1,i):
        comb[i]+=comb[i-j-1]

dp[1][0]=1


mod=10**9+7

for hh in range(1,h+1):
    for ww in range(1,w+1):
        dp[ww][hh]+=comb[ww-1]*comb[w-ww]*dp[ww][hh-1]
        dp[ww][hh]+=comb[ww-2]*comb[w-ww]*dp[ww-1][hh-1]
        dp[ww][hh]+=comb[ww-1]*comb[w-ww-1]*dp[ww+1][hh-1]
        dp[ww][hh]%=mod

print(dp[k][h])

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    dp = make_grid(H+1, W, 0)
    move = make_grid(W, W, 0)

    dp[0][0] = 1

    for case in range(2**(W-1)):
        bad_case = False
        prev_bit = -1
        for i in range(W-1):
            now_bit = (case >> i) & 1
            if now_bit == prev_bit == 1:
                bad_case = True
            prev_bit = now_bit
        if bad_case:
            continue

        for b in range(W):

            if b == 0:
                if (case >> 0) & 1:
                    move[0][1] += 1
                else:
                    move[0][0] += 1

            elif b == W - 1:
                if (case >> b - 1) & 1:
                    move[b][b - 1] += 1
                else:
                    move[b][b] += 1

            else:
                if (case >> b - 1) & 1:
                    move[b][b - 1] += 1
                elif (case >> b) & 1:
                    move[b][b + 1] += 1
                else:
                    move[b][b] += 1

    for h in range(1, H+1):
        for w in range(W):
            for i in range(W):
                dp[h][w] += dp[h-1][i] * move[i][w]

    print(dp[H][K-1]%MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W, K = MAP()

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        for S in range(1<<(W-1)):
            for k in range(W-2):
                if (S>>k)&1==1 and (S>>(k+1))&1==1:
                    break
            else:
                if j >= 1 and (S>>(j-1))&1:
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                elif j <= W-2 and (S>>j)&1:
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod

print(dp[H][K-1])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1] = 1
mod = 10**9+7
for i in range(H):
    for j in range(1, W+1):
        t_1 = 0
        t_2 = 0
        t_3 = 0
        for k in range(2**(W-1)):
            s = format(k, "b")
            p = 0
            if len(s) != W-1:
                s = "0"*(W-1-len(s)) + s
            for l in range(1, len(s)):
                if s[l-1] == "1" and s[l] == "1":
                    p = 1
                    break
            q = 0
            if p == 0:
                if 0 <= j - 2 < len(s):
                    if s[j-2] == "1":
                        t_1 += 1
                        q = 1
                if j-1 < len(s):
                    if s[j-1] == "1":
                        t_3 += 1
                        q = 1
                if q == 0:
                    t_2 += 1
        dp[i+1][j-1] += dp[i][j]*t_1
        dp[i+1][j] += dp[i][j]*t_2
        dp[i+1][j+1] += dp[i][j]*t_3
        dp[i+1][j-1] %= mod
        dp[i+1][j] %= mod
        dp[i+1][j+1] %= mod

print(dp[H][K])

Submission status: Accepted

Solution code:
def f(i):
    if i == w - 1:
        for j in range(w - 2):
            if s[j] == s[j + 1] == 1:
                return
        global x
        for j in range(w):
            if j == 0:
                if s[0] == 1:
                    x[0][1] += 1
                else:
                    x[0][0] += 1
            elif j == w - 1:
                if s[w - 2] == 1:
                    x[w - 1][w - 2] += 1
                else:
                    x[w - 1][w - 1] += 1
            else:
                if s[j - 1] == 1:
                    x[j][j - 1] += 1
                elif s[j] == 1:
                    x[j][j + 1] += 1
                else:
                    x[j][j] += 1 
        return
    s[i] = 1
    f(i + 1)
    s[i] = 0
    f(i + 1)

h, w, k = map(int, input().split())
mod = pow(10, 9) + 7
s = [0] * (w - 1)
x = [[0] * w for _ in range(w)]
if not w == 1:
    f(0)
else:
    print(1)
    exit()
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
for i in range(1, h + 1):
    for j in range(w):
        for l in range(w):
            dp[i][j] += dp[i - 1][l] * x[l][j]
            dp[i][j] %= mod
print(dp[h][k - 1])

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
Mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
n=2**(w-1)
for i in range(h):
    for j in range(w):
        for m in range(n):
            ok=True
            for k in range(w-2):
                if (m&(1<<k)) and (m&(1<<(k+1))):
                    ok=False
            if not ok:
                continue
            nj=j
            if (m & (1<<j)):
                nj=j+1
            elif j>0 and (m&(1<<(j-1))):
                nj=j-1
            dp[i+1][nj]+=dp[i][j]
            dp[i+1][nj]%=Mod
print(dp[h][K-1])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W, K = getNM()

if W == 1:
    print(1)
    exit()

# 左からi本目の右、左に橋がかかっている通り、両方に通ってない通り
bridge_right = [0] * W
bridge_left = [0] * W
not_bridge = [0] * W

for bit in range(1 << (W - 1)):
    flag = True
    for i in range(1, (W - 1)):
        if bit & (1 << i) and bit & (1 << (i - 1)):
            flag = False
    if flag:
        for i in range(W):
            if i == 0:
                if bit & (1 << i):
                    bridge_right[i] += 1
                else:
                    not_bridge[i] += 1
            elif i == W - 1:
                if bit & (1 << (i - 1)):
                    bridge_left[i] += 1
                else:
                    not_bridge[i] += 1
            else:
                if bit & (1 << i):
                    bridge_right[i] += 1
                elif bit & (1 << (i - 1)):
                    bridge_left[i] += 1
                else:
                    not_bridge[i] += 1

dp = [[0] * W for i in range(H + 1)]

dp[0][0] = 1
for i in range(1, W):
    dp[0][i] = 0

# まっすぐ降りて来た場合、右から降りてきた場合、左から降りてきた場合
for i in range(1, H + 1):
    for j in range(W):
        dp[i][j] += dp[i - 1][j] * not_bridge[j]
        if j == 0:
            dp[i][j + 1] += dp[i - 1][j] * bridge_right[j]
        elif j == W - 1:
            dp[i][j - 1] += dp[i - 1][j] * bridge_left[j]
        else:
            dp[i][j + 1] += dp[i - 1][j] * bridge_right[j]
            dp[i][j - 1] += dp[i - 1][j] * bridge_left[j]

print(dp[-1][K - 1] % mod)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
mod = 10**9+7

if w == 1:
    print(1)
    exit()

dp = [[0]*w for _ in range(h+1)]
dp[0][0] = 1
for i in range(1, h+1):
    for p in range(2**(w-1)):
        L = [0]*(w-1)
        for q in range(w-1):
            if (p >> q) & 1:
                L[q] = 1
        flag = True
        for q in range(w-2):
            if L[q] == 1 and L[q+1] == 1:
                flag = False
        if not flag:
            continue
        for j in range(w):
            if j == 0:
                if L[j] == 1:
                    dp[i][j] += dp[i-1][1]
                else:
                    dp[i][j] += dp[i-1][0]
            elif j == w-1:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][w-2]
                else:
                    dp[i][j] += dp[i-1][w-1]
            else:
                if L[j-1] == 1:
                    dp[i][j] += dp[i-1][j-1]
                elif L[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod

#print(dp)
print(dp[h][k-1])

Submission status: Accepted

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

import itertools
mod = 1000000007

h, w, k = list(map(int, input().split()))

dp = [[0]*(w) for _ in range(h+1)]

dp[0][0] = 1

for h_ in range(1, h+1):
    for bridges in itertools.product([0, 1], repeat=w-1):
        flag = 0
        for j in range(len(bridges)-1):
            if bridges[j] == 1 and bridges[j+1] == 1:
                flag = 1
                continue
        if flag == 1:
            continue
        # print(bridges)
        for w_ in range(w):
            if w_ > 0:
                if bridges[w_-1] == 1:
                    dp[h_][w_] += dp[h_-1][w_-1] % mod
                    continue
            if w_ < w-1:
                if bridges[w_] == 1:
                    dp[h_][w_] += dp[h_-1][w_+1] % mod
                    continue
            dp[h_][w_] += dp[h_-1][w_] % mod

# print(dp)

print(dp[-1][k-1] % mod)

Submission status: Accepted

Solution code:
h,w,k_=map(int,input().split())
mod=pow(10,9)+7
if w==1:
  print(1)
  exit()
# 遷移の仕方
sen=[[0]*3 for _ in range(w)]
for j in range(2**(w-1)):
  yoko=[0]*(w-1)
  for k in range(w-1):
    if (j>>k) & 1:
      yoko[k]=1
  flg=True
  for k in range(w-2):
    if yoko[k]==1 and yoko[k+1]==1:
      flg=False
      break
  if not flg:continue
  for k in range(w):
    if k==0:
      if yoko[k]==1:
        sen[k+1][0]+=1
      else:
        sen[k][2]+=1
    elif k<w-1:
      if yoko[k]==1:
        sen[k+1][0]+=1
      elif yoko[k-1]==1:
        sen[k-1][1]+=1
      else:
        sen[k][2]+=1
    else:
      if yoko[k-1]==1:
        sen[k-1][1]+=1
      else:
        sen[k][2]+=1

import numpy as np 
dp=np.zeros((h+1,w),int)
dp[0,0]=1
for i in range(h):
  dp[i+1,0]=sen[0][2]*dp[i,0]+sen[0][1]*dp[i,1]
  for j in range(1,w-1):
    dp[i+1,j]=sen[j][2]*dp[i,j]+sen[j][1]*dp[i,j+1]+sen[j][0]*dp[i,j-1]
  dp[i+1,w-1]=sen[w-1][2]*dp[i,w-1]+sen[w-1][0]*dp[i,w-2]
  dp[i+1]%=mod
print(dp[h,k_-1])
#print(dp)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,k=MI()
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
a=0
b=1
weight=[]
for i in range(100):
    weight.append(a+b)
    a,b=b,a+b
#print(weight)    
for i in range(h):
    for j in range(w):
        if 0<=j+1<w:
            left=max(j-1,0)
            right=max(w-j-3,0)
            dp[i+1][j+1]+=(dp[i][j]*weight[left]*weight[right])%mod
        if 0<=j<w:
            left=max(j-1,0)
            right=max(w-j-2,0)
            dp[i+1][j]+=(dp[i][j]*weight[left]*weight[right])%mod
        if 0<=j-1<w:
            left=max(j-2,0)
            right=max(w-j-2,0)
            dp[i+1][j-1]+=(dp[i][j]*weight[left]*weight[right])%mod
print(dp[-1][k-1]%mod)

Submission status: Accepted

Solution code:
MOD=10**9+7

def isvalid(bit):
    for t in range(W-2):
        if (bit>>t&1) and (bit>>(t+1)&1):
            return False
    return True

H,W,K=map(int,input().split())
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1

for i in range(1,H+1):
    for k in range(W):
        l,c,r=0,0,0
        for bit in range(2**(W-1)):
            if not isvalid(bit):
                continue
            if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-1 and not(bit>>k&1))or k==W-1):
                c+=1
            if (k>0) and (bit>>(k-1)&1):
                l+=1
            if (k<W-1) and (bit>>k&1):
                r+=1
        dp[i][k]=(dp[i][k]+dp[i-1][k]*c)%MOD
        if k>0:
            dp[i][k]=(dp[i][k]+dp[i-1][k-1]*l)%MOD
        if k<W-1:
            dp[i][k]=(dp[i][k]+dp[i-1][k+1]*r)%MOD
print(dp[H][K-1])

Submission status: Accepted

Solution code:
MOD=10**9+7
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1

for i in range(1,H+1):
    for k in range(W):
        l,c,r=0,0,0
        for bit in range(2**(W-1)):
            ok=True
            for t in range(W-2):
                if (bit>>t&1) and (bit>>(t+1)&1):
                    ok=False
                    break
            if not ok:
                continue
            if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-1 and not(bit>>k&1))or k==W-1):
                c+=1
            if (k>0):
                if ((k>1 and not(bit>>(k-2)&1)) or k==1) and ((k<W-1 and not(bit>>k&1))or k==W-1) and (bit>>(k-1)&1):
                    l+=1
            if (k<W-1):
                if ((k>0 and not(bit>>(k-1)&1)) or k==0) and ((k<W-2 and not (bit>>(k+1)&1))or k==W-2) and (bit>>k&1):
                    r+=1
        dp[i][k]=(dp[i][k]+dp[i-1][k]*c)%MOD
        if k>0:
            dp[i][k]=(dp[i][k]+dp[i-1][k-1]*l)%MOD
        if k<W-1:
            dp[i][k]=(dp[i][k]+dp[i-1][k+1]*r)%MOD
print(dp[H][K-1])