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: Time Limit Exceeded

Solution code:
a,b,c=map(int,input().split())
e=0
f=[[1,1]]
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[12,8,8,5,10,6,9,6,10,5,8,8,12],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
else:
    d=k[b-2]
    for i in range(0,a):
        j=0
        l=len(f)
        while j<l:
            f.append([f[j][0],f[j][1]*d[2*(f[j][0]-1)]])
            if f[j][0]-1>0:
                f.append([f[j][0]-1,f[j][1]*d[1+2*(f[j][0]-2)]])
            if f[j][0]+1<=b:
                f.append([f[j][0]+1,f[j][1]*d[2*(f[j][0]-1)+1]])
            j+=1
        else:
            del f[:l]
    else:
        for i in range(0,len(f)):
            if f[i][0]==c:
                e+=f[i][1]
        print(e%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def Calc(M):
    meta = (1,1,2,3,5,8,13,21)
    result = 1
    for i in M:
        result *= meta[i[0] - 1] * meta[W - i[0] - i[1]]
    return result % 1000000007

def Map(X, Y, M):
    if Y == H:
        if X == K + 1:
            M.append((X - 1, 1))
            return Calc(M)
        if X == K:
            M.append((X, 0))
            return Calc(M)
        if X == K - 1:
            M.append((X, 1))
            return Calc(M)
        return 0
    
    XnM = M.copy()
    XnM.append((X, 0))
    result = Map(X, Y + 1, XnM)

    if X > 1:
        XmM = M.copy()
        XmM.append((X - 1, 1))
        result += Map(X - 1, Y + 1, XmM)

    if X < W:    
        XpM = M.copy()
        XpM.append((X, 1))
        result += Map(X + 1, Y + 1, XpM)

    return result % 1000000007

ls = input().strip().split(' ')
H = int(ls[0])
W = int(ls[1])
K = int(ls[2])

print(Map(1, 1, []))

Submission status: Time Limit Exceeded

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

def func(H, W, K, y, x, v):
    if W == 1:
        return 1 if K == 0 else 0
    if y == H and x == 0:
        xx = 0
        for yy in range(H):
            if (yy, xx) in v:
                xx = xx + 1
            elif xx > 0 and (yy, xx - 1) in v:
                xx = xx - 1

        return 1 if xx == K else 0

    next_y, next_x = y, x + 1
    if next_x >= W - 1:
        next_y = next_y + 1
        next_x = 0

    result = func(H, W, K, next_y, next_x, v.copy())
    if not (x > 0 and (y, x - 1) in v):
        vv = v.copy()
        vv.update({(y, x): True})
        result += func(H, W, K, next_y, next_x, vv)

    return result % 1000000007


if __name__ == '__main__':
    H, W, K = map(int, input().split(' '))
    print(func(H, W, K - 1, 0, 0, dict()))

Submission status: Accepted

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

# 0-indexedで考える
# 縦棒はW本、横棒を置ける場所は一行あたりW - 1箇所となる
# ・iとi + 1の間に横棒を引いた場合の数
# ・iから移動せずにそのままになる場合の数
# をそれぞれ求める

# LINE[i] = iとi + 1の間に横棒を引いた場合の数。
# POINT[i] = iから横棒が出ていない場合の数
# それぞれDPで求める

H,W,K = map(int,readline().split())
DIV = 1000000007

# dp[i][j] = 間隔iまで処理したときに、j番目の間隔に棒がある(0,1)場合の数
LINE = [-1] * (W - 1)
for i in range(W - 1):
  # iとi + 1の間に棒がある場合
  dp = [[0] * 2 for j in range(W - 1)]
  if i == 0:
    dp[0][0] = 0
    dp[0][1] = 1
  else:
    dp[0][0] = 1
    dp[0][1] = 1
  for j in range(1, W - 1):
    if j == i:
      dp[j][0] = 0
      dp[j][1] = dp[j - 1][0]
    else:
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
      dp[j][1] += dp[j - 1][0]
  LINE[i] = dp[-1][0] + dp[-1][1]
  LINE[i] %= DIV

POINT = [-1] * W
# 点iからまっすぐ下がる場合の数
# iから右に棒を引く/引かない場合の数を数える
for i in range(W):
  # i - 1にもiにも棒がない場合
  dp = [[0] * 2 for j in range(W)]
  if i - 1 == 0 or i == 0:
    dp[0][0] = 1
    dp[0][1] = 0
  else:
    dp[0][0] = 1
    dp[0][1] = 1
  for j in range(1, W):
    if j == i - 1 or j == i:
      dp[j][1] = 0
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
    else:
      dp[j][0] += dp[j - 1][0] + dp[j - 1][1]
      if j == W - 1:
        dp[j][1] = 0
      else:
        dp[j][1] += dp[j - 1][0]
  POINT[i] = dp[-1][0] + dp[-1][1]
  POINT[i] %= DIV
  
# ここからDP
# dp[i][j] = あみだのi段目でjにいる場合の数

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

for i in range(1, len(dp)):
  for j in range(W):
    # jを出発点にして遷移する
    if j - 1 >= 0:
      dp[i][j] += dp[i - 1][j - 1] * LINE[j - 1]
    dp[i][j] += dp[i - 1][j] * POINT[j]
    if j + 1 < W:
      dp[i][j] += dp[i - 1][j + 1] * LINE[j]
      
    dp[i][j] %= DIV
    
print(dp[H][K - 1])

Submission status: Accepted

Solution code:
from itertools import combinations

def getval():
    h,w,k = map(int,input().split())
    return h,w,k

def main(h,w,goal):
    dp = [0 for i in range(w)]
    dp[0] = 1
    mod = 10**9 + 7
    for i in range(h):
        temp = [0 for i in range(w)]
        for j in range(w):
            for comb in combinations(range(w-1),j):
                arr = [k for k in comb]
                arr.sort()
                flag = False
                for k in range(len(arr)-1):
                    if arr[k]+1==arr[k+1]:
                        flag = True
                        break
                if flag:
                    continue
                for k in range(w):
                    if k in arr:
                        temp[k+1] += dp[k]
                        temp[k+1] %= mod
                    elif k-1 in arr:
                        temp[k-1] += dp[k]
                        temp[k-1] %= mod
                    else:
                        temp[k] += dp[k]
                        temp[k] %= mod
        dp = temp
    print(dp[goal-1]%mod)
                
                
if __name__=="__main__":
    h,w,k= getval()
    main(h,w,k)

Submission status: Accepted

Solution code:
# 解説と下記を参考に作成
# https://atcoder.jp/contests/abc113/submissions/15821617
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    fibo = [1, 2, 3, 5, 8, 13, 21]
    for h in range(H):
        for w in range(W):
            if dp[h][w] == 0:
                continue
            for i in range(3):
                new_w = w - 1 + i
                if not 0 <= new_w < W:
                    continue
                l, r = min(w, new_w), max(w, new_w)
                tmp = fibo[max(l - 1, 0)] * fibo[max(W - 1 - (r + 1), 0)]
                dp[h + 1][new_w] += dp[h][w] * tmp
                dp[h + 1][new_w] %= mod
    print(dp[-1][K - 1])


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    solve(H, W, K)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
# 解説と下記を参考に作成
# https://atcoder.jp/contests/abc113/submissions/15821617
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    for h in range(H):
        for w in range(W):
            if dp[h][w] == 0:
                continue
            for i in range(3):
                new_w = w - 1 + i
                if not 0 <= new_w < W:
                    continue

                def cnt_tmp(n, r, l, flg):
                    re = 0
                    if n >= W - 2:
                        if r <= n <= l:
                            return 1
                        if flg:
                            return 1
                        else:
                            return 2
                    if r <= n <= l:
                        return cnt_tmp(n + 1, r, l, False)
                    re += cnt_tmp(n + 1, r, l, False)
                    re += cnt_tmp(n + 1, r, l, True) if not flg else 0
                    return re

                tmp = cnt_tmp(0, min(w, new_w) - 1, max(w, new_w), False)
                dp[h + 1][new_w] += dp[h][w] * tmp
                dp[h + 1][new_w] %= mod
    # for dpi in dp:
    #     print(dpi)
    print(dp[-1][K - 1])


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    solve(H, W, K)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:

import sys
import itertools

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

if w==1:
    print(1)
    sys.exit()
    
mod=10**9+7

ww=[]
for i in itertools.product([0,1], repeat=w-1):
    yn=""
    for wi in range(w-2):
        if i[wi]==1 and i[wi+1]==1:
            yn="no"
            break
    if yn=="" :
        ww.append(i)

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

for i in range(h):
    for wi in ww:
        j=0
        if wi[j]==1:
            dp[i+1][j]=(dp[i+1][j]+dp[i][j+1])%mod
        else:    
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod

        for j in range(1,w-1):
            if wi[j-1]==1:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j-1])%mod
            elif wi[j]==1:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j+1])%mod
            else:    
                dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        j=w-1
        if wi[j-1]==1:
            dp[i+1][j]=(dp[i+1][j]+dp[i][j-1])%mod
        else:    
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
                
print(dp[h][k-1])

Submission status: Accepted

Solution code:
"""
dp[i][j] => i回目の移動が終了したタイミングでj列目にいる場合の数
dp[i][j] 
= dp[i-1][j-1]*(j-1列目とj列目の間に横棒があるような横棒の配置パターン数)
+ dp[i-1][j+1]*(j+1列目とj列目の間に横棒があるような横棒の配置パターン数)
+ dp[i-1][j]*(j列目の両サイドに横棒がないような横棒の配置パターン数)
"""

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

"""
横棒の配置パターンを前計算しておく
patternA[i] => i列目とi-1列目の間に横棒があるような横棒の配置パターン数
patternB[i] => i列目の両サイドに横棒がないような横棒の配置パターン数
"""
patternA = [0]*(W)
patternB = [0]*(W)
for i in range(2**(W-1)):
    pattern = format(i,"0"+str(W-1)+"b")
    for j in range(1,W-1):
        if pattern[j] == "1" and pattern[j-1]=="1":
            break
    else:
        for j in range(W-1):
            if pattern[j] == "1":
                patternA[j+1] += 1

        for j in range(W):
            if j == 0:
                if pattern[j] == "0":
                    patternB[j] += 1
            elif 0 < j < W-1:
                if pattern[j-1] == "0" and pattern[j] == "0":
                    patternB[j] += 1
            elif j == W-1:
                if pattern[j-1] == "0":
                    patternB[j] += 1

dp = [[0]*W for _ in range(H+1)]
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-1]*patternA[j]%mod
        #右上から降りてくるパターン
        if j < W-1:
            dp[i][j] += dp[i-1][j+1]*patternA[j+1]%mod
        
        #真上から降りてくるパターン
        dp[i][j] += dp[i-1][j]*patternB[j]%mod

        dp[i][j] %= mod

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

Submission status: Accepted

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

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


def fib(n):
    if n <= 1:
        return 1
    return fib(n-1) + fib(n-2)


for i in range(1, H+1):
    for j in range(W):
        left = j
        right = W - j - 1

        dp[i][j] = dp[i-1][j] * fib(left) * fib(right)

        if j > 0:
            dp[i][j] += dp[i-1][j-1] * fib(left-1) * fib(right)

        if j < W-1:
            dp[i][j] += dp[i-1][j+1] * fib(left) * fib(right - 1)

        dp[i][j] %= mod

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

Submission status: Accepted

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

    if w == 1:
        print(1)
        exit()
    if w == 2:
        print(pow(2, h-1, mod))
        exit()

    k -= 1

    fibo = [1, 2, 3, 5, 8, 13, 21]

    dp = [0] * w
    dp[0] = 1
    for _ in range(h):
        new_dp = [0] * w
        new_dp[0] = (dp[0] * fibo[w-2] + dp[1] * fibo[w-3]) % mod
        new_dp[1] = (dp[0] * fibo[w-3]) % mod
        new_dp[w-1] = (dp[w-1] * fibo[w-2] + dp[w-2] * fibo[w-3]) % mod
        new_dp[w-2] += (dp[w-1] * fibo[w-3]) % mod
        for i in range(1, w-1):
            new_dp[i] += ((fibo[i-1] * fibo[w-i-2]) * dp[i]) % mod
        for i in range(1, w-2):
            new_dp[i] += (fibo[i-1] * fibo[w-i-3]) * dp[i+1]
            new_dp[i] %= mod
            new_dp[i+1] += (fibo[i-1] * fibo[w-i-3]) * dp[i]
            new_dp[i+1] %= mod
        dp = new_dp

    print(dp[k] % mod)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - Number of Amidakuji
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
H,W,K = map(int,readline().split())
facts = [1,1,2,3,5,8,13,21,34]
# a = [0]
# b = [1]
# for i in range(W):
#     a.append(b[i])
#     b.append(a[i]+b[i])

dp = [0] * W
dp[0] = 1
for _ in range(H):
    ndp = [0]*W
    for w in range(W):
        ndp[w] += dp[w] * facts[w] * facts[W-w-1]
        if w > 0:
            ndp[w] += dp[w-1] * facts[w-1] * facts[W-w-1] 
        if w < W-1:
            ndp[w] += dp[w+1] * facts[w] * facts[W-w-2]
        ndp[w] %= MOD
    dp = ndp
    
print(dp[K-1])

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
mod = 10**9+7
dp = W*[0]
dp[0] = 1
fib = [1,1,2,3,5,8,13,21,34,55,89]

for h in range(H):
  t = W*[0]
  for w in range(W):
    if 0<w:
      t[w]+=dp[w-1]*fib[w-1]*fib[W-w-1]
    t[w]+=dp[w]*fib[w]*fib[W-w-1]
    
    if w<W-1:
      t[w]+=dp[w+1]*fib[w]*fib[W-w-2]
    t[w]%=mod
  dp = t

print(dp[K-1])

Submission status: Accepted

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

mod = 10**9 + 7
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)):
            ok = True
            for k in range(W-2):
                if bit & (1 << k) and bit & (1 << (k+1)):
                    ok = False
            if not ok:
                continue

            jj = j
            if j > 0 and bit & (1 << (j-1)):
                jj -= 1
            elif j < W - 1 and bit & (1 << j):
                jj += 1
            dp[i+1][jj] += dp[i][j]
            dp[i+1][jj] %= mod


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

Submission status: Accepted

Solution code:
"""
memo1[i] => i列目とi+1列目の間に横棒があるような場合の数
memo2[i] => i列目の両サイドに横棒がないような場合の数
"""

H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
mod = 10**9 +7
memo1 = [0]*(W-1)
memo2 = [0]*W
for i in range(2**(W-1)):
    #bin(i)が横棒の配置パターンを表す
    binI = format(i,"0"+str(W-1)+"b")
    #パターンが正しいかを確かめる
    for j in range(W-2):
        if binI[j]=="1" and binI[j+1]=="1":
            break
    else:
        for j in range(W-1):
            if binI[j] == "1":
                memo1[j] += 1
        if binI[0] == "0":
            memo2[0] += 1
        if binI[-1] == "0":
            memo2[-1] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j]=="0":
                memo2[j] += 1


#dp[i][j] => i回目の移動が終わったタイミングで、j列目にいるような場合の数
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        #真下に移動する場合の数
        dp[i+1][j] += dp[i][j]*memo2[j]
        dp[i+1][j] %= mod

        #右に移動する場合の数
        if j != W-1:
            dp[i+1][j+1] += dp[i][j]*memo1[j]
            dp[i+1][j+1] %= mod

        #左に移動する場合の数
        if j != 0:
            dp[i+1][j-1] += dp[i][j]*memo1[j-1]
            dp[i+1][j-1] %= mod

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

Submission status: Accepted

Solution code:
import sys

h, w, k = map(int, input().split())
mod = 10 ** 9 + 7
if w == 1:
    print(1)
    sys.exit()
row = [0 for i in range(w + 1)]
row[0] = 1
row[1] = 1
for i in range(w - 1):
    row[i + 2] = row[i + 1] + row[i]

dp = [[0 for i in range(w)] for j in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if j == 0:
            dp[i + 1][j] = dp[i][j] * row[w - 1] + dp[i][j + 1] * row[w - 2]
            dp[i + 1][j] %= mod
        elif j == w - 1:
            dp[i + 1][j] = dp[i][j] * row[w - 1] + dp[i][j - 1] * row[w - 2]
            dp[i + 1][j] %= mod
        else:
            dp[i + 1][j] = dp[i][j - 1] * row[j - 1] * row[w - j - 1] + dp[i][j] * row[j] * row[w - j - 1] + dp[i][j + 1] * row[j] * row[w - j - 2]
            dp[i + 1][j] %= mod
print(dp[h][k - 1])

Submission status: Accepted

Solution code:
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


mod = 10 ** 9 + 7


def main():

    H, W, K = in_nn()

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

    comb_t = itertools.product(range(2), repeat=W - 1)
    comb = [[0 for _ in range(3)] for _ in range(W)]

    for c in comb_t:

        f = True
        for i in range(W - 2):
            if c[i] == c[i + 1] == 1:
                f = False
                break

        if f:
            for i in range(W):

                if i - 1 >= 0 and c[i - 1] == 1:
                    comb[i][0] += 1
                elif i < W - 1 and c[i] == 1:
                    comb[i][2] += 1
                else:
                    comb[i][1] += 1

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

    for y in range(H):
        for x in range(W):

            now = dp[y][x]
            dp[y + 1][x] += now * comb[x][1]
            dp[y + 1][x] %= mod
            if 0 <= x - 1 < W:
                dp[y + 1][x - 1] += now * comb[x][0]
                dp[y + 1][x - 1] %= mod
            if 0 <= x + 1 < W:
                dp[y + 1][x + 1] += now * comb[x][2]
                dp[y + 1][x + 1] %= mod

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
15,8,5の場合：
何回右に移動するか、何回左に移動するか。
dp[i][j] => i回目下降が終わった時点で、j列目にいる場合の数
memo[j] => 特定の高さを見たときに、j列目とj+1列目の間に横棒があるような横棒配置パターン数
memo2[j] => j列目の左右に横棒がないような場合の数
"""
mod = 10**9 +7
H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
memo = [0]*(W-1)
memo2 = [0]*(W-1)
cnt = 0
for i in range(2**(W-1)):
    binI = format(i,"0"+str(W-1)+"b")
    #パターンの有効性をチェックする
    for j in range(W-2):
        if binI[j] == "1" and binI[j+1] == "1":
            break
    else:
        cnt += 1
        for j in range(W-1):
            if binI[j] == "1":
                memo[j] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j] =="0":
                memo2[j] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1

for i in range(H):
    for j in range(W):
        #右の列に移動する
        if j != W-1:
            dp[i+1][j+1] += memo[j]*dp[i][j]%mod
            dp[i+1][j+1] %= mod
        #左の列に移動する
        if j != 0:
            dp[i+1][j-1] += memo[j-1]*dp[i][j]%mod
            dp[i+1][j-1] %= mod
        #真下に移動する
        if j == 0:
            dp[i+1][j] += (cnt-memo[j])*dp[i][j]%mod
        elif j == W-1:
            dp[i+1][j] += (cnt-memo[j-1])*dp[i][j]%mod
        else:
            dp[i+1][j] += memo2[j]*dp[i][j]%mod
        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
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            # Check valid connection
            ok = True
            for l in range(W - 2):
                if (k >> l) & 1 and k >> (l + 1) & 1:
                    ok = False

            if not ok:
                continue

            if j > 0 and k >> (j - 1) & 1:
                dp[i + 1][j - 1] += dp[i][j]
                dp[i + 1][j - 1] %= MOD
            elif j < W - 1 and k >> 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[-1][K - 1])

Submission status: Accepted

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

comb = []
for bit in range(1 << w - 1):
    ok = True
    for j in range(w - 2):
        if bit >> j & 1 and bit >> j + 1 & 1:
            ok = False
    if ok:
        comb.append(bit)

dp[0] = 1
for i in range(h):
    next = [0] * w
    for bit in comb:
        moved = [False] * w
        for j in range(w):
            if bit >> j & 1:
                next[j + 1] += dp[j]
                next[j] += dp[j + 1]
                moved[j] = moved[j + 1] = True
            elif not moved[j]:
                next[j] += dp[j]
    dp = next
print(dp[k - 1] % mod)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

H,W,K = MI()
mod = 10**9+7

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

fib = [1,1,2,3,5,8,13,21]  # fib[i] = i本のあみだくじの、ある列に横線を引く方法の数

dp = [[0]*(W+1) for _ in range(H+1)]  # dp[i][j] = i段横線を引いたときに1からKに至るような横線の引き方
dp[0][1] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        if j == 1:
            dp[i][j] = dp[i-1][j+1]*fib[W-j-1] + dp[i-1][j]*fib[W-j]
            dp[i][j] %= mod
        elif j == W:
            dp[i][j] = dp[i-1][j-1]*fib[j-2] + dp[i-1][j]*fib[j-1]
            dp[i][j] %= mod
        else:
            dp[i][j] = dp[i-1][j-1]*fib[j-2]*fib[W-j] + dp[i-1][j+1]*fib[j-1]*fib[W-j-1] + dp[i-1][j]*fib[W-j]*fib[j-1]
            dp[i][j] %= mod

print(dp[H][K])

Submission status: Accepted

Solution code:
import sys

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

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

fn = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

for i in range(1, h + 1):
    for j in range(w):
        dp[i][j] = dp[i - 1][j] * fn[j] * fn[w - j - 1]
        if j < w - 1:
            dp[i][j] += dp[i - 1][j + 1] * fn[j] * fn[w - j - 2]
        if 0 < j:
            dp[i][j] += dp[i - 1][j - 1] * fn[j - 1] * fn[w - j - 1]
        dp[i][j] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
h, w, k = [int(x) for x in input().split()]
dp = [[0] * w for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for b in range(1 << (w-1)):
        ok = True
        for s in range(w-2):
            if b >> s & 1 and b >> (s+1) & 1:
                ok = False
        if ok:            
            for j in range(w):
                if j > 0 and b >> (j-1) & 1:
                    dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
                elif j+1 < w and b >> j & 1:
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD
                else:
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD

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

Submission status: Accepted

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

dp[0] = 1
for i in range(h):
    next = [0] * w
    for bit in range(1 << w - 1):
        ok = True
        for j in range(w - 2):
            if bit >> j & 1 and bit >> j + 1 & 1:
                ok = False
        if ok:
            moved = [False] * w
            for j in range(w):
                if bit >> j & 1:
                    next[j + 1] += dp[j]
                    next[j] += dp[j + 1]
                    moved[j] = moved[j + 1] = True
                elif not moved[j]:
                    next[j] += dp[j]
    dp = next
print(dp[k - 1] % mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,K = MI()
mod = 10**9+7

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

fib = [1,1,2,3,5,8,13,21,34]

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][1] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        if W == 2:
            if j == 1:
                dp[i][j] = dp[i-1][j] + dp[i-1][j+1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                dp[i][j] %= mod
        else:
            if j == 1:
                dp[i][j] = dp[i-1][j+1]*fib[W-2] + dp[i-1][j]*fib[W-j]
                dp[i][j] %= mod
            elif j == W:
                dp[i][j] = dp[i-1][j-1]*fib[W-2] + dp[i-1][j]*fib[j-1]
                dp[i][j] %= mod
            else:
                dp[i][j] = dp[i-1][j-1]*fib[j-2]*fib[W-j] + dp[i-1][j+1]*fib[j-1]*fib[W-j-1] + dp[i-1][j]*(fib[W-j]*fib[j-1])
                dp[i][j] %= mod

print(dp[H][K])

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
remv = [1,1,2,3,5,8,13,21]

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

MOD = 10**9+7
for i in range(h):
    for wi in range(w):
        left = wi
        right = w-wi-1
        com = remv[left] * remv[right]
        dp[i+1][wi] += dp[i][wi]*com
        dp[i+1][wi] %= MOD

        if wi > 0:
            left = wi-1
            right = w-wi-1
            com = remv[left] * remv[right]
            dp[i+1][wi-1] += dp[i][wi]*com
            dp[i+1][wi-1] %= MOD

        if wi < w-1:
            left = wi
            right = w-(wi+1)-1
            com = remv[left] * remv[right]
            dp[i+1][wi+1] += dp[i][wi]*com
            dp[i+1][wi+1] %= MOD


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

Submission status: Accepted

Solution code:
import itertools

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

# 縦棒を0-indexで考える
# dp[i][j] := 上から高さi(0,1,...,h)までの横棒を配置した時に、
#             0(問題文では1)からスタートしてjで終わるようなものの個数

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

# 縦線が1本の場合、以下の議論が成立しない
if w == 1:
    print(1)
    exit()

bridges = list(itertools.product([0, 1], repeat=w - 1))
# print(bridges)

for i in range(h):
    for bridge in bridges:

        # 橋が隣り合っていてはいけない
        tf = True
        for j in range(w - 2):
            if bridge[j] == 1 and bridge[j + 1] == 1:
                tf = False
                break
        if tf == False:
            continue

        for j in range(w):
            # 左端について
            if j == 0:
                # 橋がある時、右から流入
                if bridge[0] == 1:
                    dp[i + 1][j] += dp[i][j + 1]
                # 橋がない時、上から流入
                else:
                    dp[i + 1][j] += dp[i][j]

            # 右端について
            elif j == w - 1:
                # 橋がある時、左から流入
                if bridge[-1] == 1:
                    dp[i + 1][j] += dp[i][j - 1]
                # 橋がない時、上から流入
                else:
                    dp[i + 1][j] += dp[i][j]

            #　両端以外について
            else:
                # 両サイドに橋がない場合
                if bridge[j - 1] == 0 and bridge[j] == 0:
                    dp[i + 1][j] += dp[i][j]
                # 左だけ橋がある場合
                elif bridge[j - 1] == 1 and bridge[j] == 0:
                    dp[i + 1][j] += dp[i][j - 1]
                # 右だけ橋がある場合
                elif bridge[j - 1] == 0 and bridge[j] == 1:
                    dp[i + 1][j] += dp[i][j + 1]

            dp[i + 1][j] %= mod

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

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MOD, p, cnt = 10**9+7, [0]*W, 0
for bit in range(1<<(W-1)):
    s0 = bit&1
    flg=True
    for w in range(1, W-1):
        if (bit>>w)&1 and s0 == 1:flg=False; break
        s0 = (bit>>w)&1
    if flg:
        cnt += 1
        for w in range(W - 1):
            if (bit >> w)&1:p[w] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if w:
            dp[h+1][w-1] += dp[h][w]*p[w-1]
            dp[h+1][w-1] %= MOD
        if w-(W - 1):
            dp[h+1][w+1] += dp[h][w]*p[w]
            dp[h+1][w+1] %= MOD
        dp[h+1][w]+=dp[h][w]*(cnt-p[w-1]-p[w])
        dp[h+1][w]%=MOD
print(dp[H][K-1])

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
dp=[[0 for _ in range(w)]for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
    for bit in range(2**(w-1)):
        bit=bin(bit)[2:].zfill(w-1)
        f=0
        for j in range(w-2):
            if bit[j]=='1' and bit[j+1]=='1':
                f=1
                break
        if f:
            continue
        for j in range(w):
            if j==0:
                dp[i+1][j]+=dp[i][j+1] if bit[0]=='1' else dp[i][j]
            elif j==w-1:
                dp[i+1][j]+=dp[i][j-1] if bit[-1]=='1' else dp[i][j]
            else:
                dp[i+1][j]+=dp[i][j]*(bit[j-1]=='0' and bit[j]=='0')
                dp[i+1][j]+=dp[i][j-1]*(bit[j-1]=='1')
                dp[i+1][j]+=dp[i][j+1]*(bit[j]=='1')
            dp[i+1][j]%=mod
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
W2 = W-1
c = [0] * (W2+1)
cnt = 0
MOD = 10**9 + 7
for bit in range(1 << W2):
    s0 = bit&1
    flg=True
    for i in range(1, W2):
        if (bit>>i)&1 and s0 == 1:
            flg = False
            break
        s0 = (bit>>i)&1
    if flg:
        cnt += 1
        for i in range(W2):
            if (bit >> i)&1:
                c[i] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for i in range(W):
        if i != 0:
            dp[h+1][i-1] += dp[h][i]*c[i-1]
            dp[h+1][i-1] %= MOD
        if i != W-1:
            dp[h+1][i+1] += dp[h][i]*c[i]
            dp[h+1][i+1] %= MOD
        dp[h+1][i] += dp[h][i]*(cnt-c[i-1]-c[i])
        dp[h+1][i] %= MOD
print(dp[H][K-1])