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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)
#D
def D():
    h,w,k = LI()
    dp = [[0 for i in range(w)] for j in range(h+1)]
    dp[0][0] = 1
    p = [1 for i in range(w+1)]
    for i in range(w):
        p[i+1] = p[i]*2
    l = [i for i in range(p[w-1])]
    i = 0
    while i < len(l):
        a = l[i]
        for j in range(w):
            if a&p[j] and a&p[j+1]:
                l.pop(i)
                i -= 1
                break
        i += 1
    d = [[0 for i in range(3)] for j in range(w)]
    for j in range(w):
        for s in l:
            if 0 < j < w-1:
                if p[j]&s:
                    d[j][2] += 1
                elif p[j-1]&s:
                    d[j][0] += 1
                else:
                    d[j][1] += 1
            elif j == 0:
                if p[j]&s:
                    d[j][2] += 1
                else:
                    d[j][1] += 1
            else:
                if p[j-1]&s:
                    d[j][0] += 1
                else:
                    d[j][1] += 1
    for i in range(h):
        for j in range(w):
            dp[i+1][j] += d[j][1]*dp[i][j]
            dp[i+1][j] %= mod
            if j > 0:
                dp[i+1][j-1] += d[j][0]*dp[i][j]
                dp[i+1][j-1] %= mod
            if j < w-1:
                dp[i+1][j+1] += d[j][2]*dp[i][j]
                dp[i+1][j+1] %= mod
    print(dp[h][k-1])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,m = LI()
    v = LIR(m)
    for i in range(m):
        v[i] = [v[i][0],v[i][1],i]
    v.sort(key = lambda x:x[1])
    f = [0 for i in range(n+1)]
    ans = [None for i in range(m)]
    for p,y,i in v:
        f[p] += 1
        s = "{:0>6}".format(p)
        t = "{:0>6}".format(f[p])
        ans[i] = s+t
    for i in ans:
        print(i)
#D
def D():
    h,w,k = LI()
    dp = [[0 for i in range(w)] for j in range(h+1)]
    dp[0][0] = 1
    p = [1 for i in range(w+1)]
    for i in range(w):
        p[i+1] = p[i]*2
    l = [i for i in range(p[w-1])]
    i = 0
    while i < len(l):
        a = l[i]
        for j in range(w):
            if a&p[j] and a&p[j+1]:
                l.pop(i)
                i -= 1
                break
        i += 1
    for i in range(h):
        for j in range(w):
            a = 0
            b = 0
            c = 0
            for s in l:
                if 0 < j < w-1:
                    if p[j]&s:
                        c += 1
                    elif p[j-1]&s:
                        a += 1
                    else:
                        b += 1
                elif j == 0:
                    if p[j]&s:
                        c += 1
                    else:
                        b += 1
                else:
                    if p[j-1]&s:
                        a += 1
                    else:
                        b += 1
            dp[i+1][j] += b*dp[i][j]
            dp[i+1][j] %= mod
            if j > 0:
                dp[i+1][j-1] += a*dp[i][j]
                dp[i+1][j-1] %= mod
            if j < w-1:
                dp[i+1][j+1] += c*dp[i][j]
                dp[i+1][j+1] %= mod
    print(dp[h][k-1])
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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


def transition(w):
    X = [1, 2, 3, 5, 8, 13, 21, 34]
    if w >= 0:
        return X[w]
    else:
        return 1


# h行w列に到達する方法
dp = [[0] * W for h in range(H + 1)]
dp[0][0] = 1

for h in range(H):
    for w in range(W):
        # 真下へ
        dp[h + 1][w] += dp[h][w] * (transition(w - 1) * transition(W - w - 2))
        dp[h + 1][w] %= MOD

        # 右下へ
        if w + 1 < W:
            dp[h + 1][w + 1] += dp[h][w] * (transition(w - 1) * transition(W - w - 3))
            dp[h + 1][w + 1] %= MOD

        # 左下へ
        if w - 1 >= 0:
            dp[h + 1][w - 1] += dp[h][w] * (transition(w - 2) * transition(W - w - 2))
            dp[h + 1][w - 1] %= MOD

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

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * W for i 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)):
            flag = True
            if '11' in bin(k):
                flag = False
            if flag:
                if j >= 1 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:
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(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            ok = True
            if '11' in bin(k):
                ok = False
            if ok:
                if j >= 1 and ((k >> (j - 1)) & 1):
                    dp[i + 1][j - 1] += dp[i][j]
                    dp[i + 1][j - 1] %= mod
                    #print(1, i, bin(k), j, dp)
                    
                elif j <= W -2 and ((k >> j) & 1):
                    dp[i + 1][j + 1] += dp[i][j]
                    dp[i + 1][j + 1] %= mod
                    #print(2, i, bin(k), j, dp)
                    
                else:
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j] %= mod
                    #print(3, i, bin(k), j, dp)
            
print(dp[H][K - 1])

Submission status: Accepted

Solution code:


H,W,K = [int(n) for n in input().split()]
memo = [[0 for _ in range(W)] for __ in range(H+1)]
memo[0][0] = 1
MOD = 10**9 + 7
for h in range(1,H+1):
    for pt in range((1 << W-1)):#1 == 線あり 0 == 線なし　とする
        # pts = bin(pt)[2:]
        # pts = pts[::-1]#反転
        if "11" in bin(pt): continue
        #各パターンの時の各線の計算
        goto = [i for i in range(W)]
        for i in range(W):
            if (1 << i) & pt:
                goto[i], goto[i + 1] = goto[i + 1], goto[i]
        for i in range(W):
            memo[h][goto[i]] += memo[h-1][i]
            memo[h][goto[i]] %= MOD


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

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
dp = []
for i in range(H+1):
  L = [0]*W
  dp.append(L)
fb = [1,1]
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1
if W != 1:
  for i in range(1,H+1):
    for j in range(W):
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7))

Submission status: Accepted

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

mo=10**9 +7
p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            return pat(x-2)+pat(x-1)

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
#a(h,x)
p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            return pat(x-2)+pat(x-1)
        
for j in range(1):
    0
mo=10**9 +7

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    #a[i][0]=a[i-1][0]*pat(-1)*pat(h-1)+a[i-1][1]*pat(0)*pat(h-2)
    #a[i][w-1]=a[i-1][w-2]*pat(w-3)*pat(h-w+1)+a[i-1][w-1]*pat(w-1-1)*pat(h-w)
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)
#print(a)

Submission status: Accepted

Solution code:
h, w, K = [int(item) for item in input().split()]

ans = [[0 for i in range(w)] for j in range(h+1)]
pats = []

def layer_pattern(w, pat):
  if w == 0:
    for i in range(len(pat) -1):
      if pat[i] == 1 and pat[i+1] == 1:
        return False
    pats.append([0] + pat + [0])
    return True
  layer_pattern(w-1, pat + [0])
  layer_pattern(w-1, pat + [1])

layer_pattern(w-1, [])

for i in range(h+1):
  if i == 0:
    ans[0][0] = 1
  else:
    for pat in pats:
      for k in range(len(pat)):
        if k == len(pat)-1:
          continue
        elif pat[k] == 0 and pat[k+1] == 0:
          ans[i][k] += ans[i-1][k]
        elif pat[k] == 1 and pat[k+1] == 0:
          ans[i][k] += ans[i-1][k-1]
        elif pat[k] == 0 and pat[k+1] == 1:
          ans[i][k] += ans[i-1][k+1]
        else:
          print("cannot be happen")
          break

print(ans[h][K-1] % 1000000007)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
A = [[0] * (W + 2) for i in range(H + 1)]
A[0][1] = 1
def multiple(N):
    temp = [1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    return (temp[N + 1])


for i in range(1, H + 1):
    for j in range(1, W + 2):
        if j < 1 or j > W:
            A[i][j] = 0
        else:
            A[i][j] = (A[i - 1][j - 1] * (multiple(j - 2) * multiple(W - j)) +
                       A[i - 1][j] * (multiple(j - 1) * multiple(W - j)) +
                       A[i - 1][j + 1] * (multiple(j - 1) * multiple(W - j - 1))) % mod
print(A[H][K])

Submission status: Accepted

Solution code:
H,W,K = tuple(map(int,input().split()))
m = 1000000007
def get (bou_no_kazu):
    if bou_no_kazu == 2 or bou_no_kazu ==3:
        return bou_no_kazu
    else:
        return get(bou_no_kazu-1) + get(bou_no_kazu-2)

def n(nodes,from_idx,to_idx):
    ret = nodes[from_idx]
    ## print("r",ret)
    if min(from_idx,to_idx) > 1:
        #print("left")
        ret *= get(min(from_idx,to_idx))
    if max(from_idx,to_idx) < W-2:
        #print("right")
        ret *= get(W-max(from_idx,to_idx)-1)
    return ret
    
prev_node = [1]*1+[0]*(W-1)
next_node = [1]*W

for i in range(H):
    for j in range(W):
        #print(prev_node,next_node)
        next_node[j] = n(prev_node,j,j)
        if j-1 >= 0:
            next_node[j] += n(prev_node,j-1,j)
        if j+1 <= W-1:
            next_node[j] += n(prev_node,j+1,j)
    #print(prev_node)
        
    prev_node = [int(i)%m for i in next_node.copy()]
#print(next_node)
print(int(prev_node[K-1]))

Submission status: Accepted

Solution code:
def f(n):
    # 縦線n本で構成できる横線の組み合わせ
    if n <= 1: return 1
    return f(n - 1) + f(n - 2)


MOD = 10 ** 9 + 7

H, W, K = map(int, input().split())
K -= 1
# 0-indexed

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k]
# h段のあみだくじで横線kに到達する本数

for h in range(H):
    # h: 移動前の高さ
    for i in range(W):
        # i: 移動前の縦線
        if i >= 1:
            dp[h + 1][i - 1] += dp[h][i] * f(i - 1) * f(W - 1 - i)
            dp[h + 1][i - 1] %= MOD
        dp[h + 1][i] += dp[h][i] * f(i) * f(W - 1 - i)
        dp[h + 1][i] %= MOD
        if i < W - 1:
            dp[h + 1][i + 1] += dp[h][i] * f(i) * f(W - 2 - i)
            dp[h + 1][i + 1] %= MOD

print(dp[H][K])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

H, W, K = map(int, input().split())
K -= 1
# 0-indexed

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k]
# h段のあみだくじで横線kに到達する本数

for h in range(H):
    # h: 移動前の高さ
    for b in range(1 << (W - 1)):
        # 各段はW - 1箇所の横線配置位置をもつ

        if '11' in bin(b): continue
        # 横線同士がつながっているケースは不適

        goto = [i for i in range(W)]
        # goto[i]: 縦線iからの移動先

        for j in range(W - 1):
            # j: 横線の番号 かつ 横線の左側の縦線の番号
            if (b >> j) & 1 == 1:
                # 横線が存在する場合
                goto[j], goto[j + 1] = goto[j + 1], goto[j]
        # gotoで横線配置bによる移動を表現する

        for i in range(W):
            # i: 移動前の縦線
            dp[h + 1][goto[i]] += dp[h][i]
            dp[h + 1][goto[i]] %= MOD

print(dp[H][K])

Submission status: Accepted

Solution code:
# https://misteer.hatenablog.com/entry/ABC113

MOD = 10 ** 9 + 7

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

K -= 1
# 以降縦棒の番号は0-indexedで扱う

dp = [[0 for _ in range(W)] for _ in range(H + 1)]
dp[0][0] = 1
# dp[h][k]
# 横線h段からなるあみだくじで、0がkに来るものの数

for h in range(1, H + 1):
    # 移動後の高さh
    for b in range(1 << (W - 1)):
        if '11' in bin(b): continue

        perm = [i for i in range(W)]
        # 0-indexedの到達位置

        for i in range(W - 1):
            if (b >> i) & 1:
                perm[i], perm[i + 1] = perm[i + 1], perm[i]

        for i in range(W):
            dp[h][perm[i]] += dp[h - 1][i]
            dp[h][perm[i]] %= MOD

print(dp[H][K])

Submission status: Accepted

Solution code:
H, W, K = [int(x) for x in input().split()]
div = 1000000007


def baai(L):
    if L == []:
        return 1
    elif L == [0]:
        return 2
    elif L == [1]:
        return 1
    elif L == [0, 0]:
        return 3
    elif len(L) == 2:
        return 1

    if L[0:2] == [1, 0]:
        return baai(L[2:])
    elif L[0:2] == [0, 1]:
        return baai(L[1:])
    elif L[0:2] == [0, 0]:
        return baai(L[2:])+baai(L[1:])
    else:
        print("hoge", L)
        return 0


ans = [0]*(H+1)                       # 高さnに対するあみだくじ本数
dp = [[0]*W for _ in range(H)]


for i in range(H):
    for j in range(W):
        # print(i, j)
        if j-1 > i:
            break
        elif i == 0:
            if j == 0:
                dp[i][j] = baai([0]*(W-2))
            else:
                buf = [0] * (W-1)
                buf[0] = 1
                dp[i][j] = baai(buf)
            dp[i][j] = dp[i][j] % div
            continue

        buf = [0]*W
        buf[j] = 1
        dp[i][j] += dp[i-1][j]*baai(buf)
        if j-1 >= 0:
            buf = [0]*(W-1)
            buf[j-1] = 1
            dp[i][j] += dp[i-1][j-1]*baai(buf)
        if j+1 < W:
            buf = [0]*(W-1)
            buf[j] = 1
            dp[i][j] += dp[i-1][j+1]*baai(buf)
        dp[i][j] = dp[i][j] % div

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

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
# 長さ wの配列
dp = [1] + [0] * (w - 1)
 
# ????フィボナッチ数
facts = [1, 1, 2, 3, 5, 8, 13, 21, 34]
 
# h（高さ）だけ繰り返し 
for _ in range(h):
    # ndpは長さwの[0]の配列、ワークエリア
    ndp = [0] * w
    # w（縦線の数）だけ繰り返し
    for b in range(w):
        # bがゼロより大きいとき＝左端の縦線にいないとき
        if b > 0:
            # １つ左の縦線から移ってくるとき
            # ndpのb番目は、dpのb-1番目×フィボナッチ数のｂ－１番目×フィボナッチ数のw-b-1番目
            # フィボナッチ数の積なのは、通らない縦線の組み合わせ数であるため
            ndp[b] += dp[b - 1] * facts[b - 1] * facts[w - b - 1]
        # ndpのb番目にdpのb番目×フィボナッチ数のb番目×フィボナッチ数のw-b-1番目
        # そのまま下がってくるとき
        ndp[b] += dp[b] * facts[b] * facts[w - b - 1]
        # b が w-1より小さいとき＝右端の縦線にいないとき
        if b < w - 1:
            # １つ右の縦線から移ってくるパターンの数は
            ndp[b] += dp[b + 1] * facts[b] * facts[w - b - 2]
        ndp[b] %= 1000000007
    dp = ndp
 
print(dp[k - 1])


#疑問点：フィボナッチ数である理由

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

fibs = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
def getFib(i):
    return fibs[i+2]

numLs, numCs, numRs = [0]*W, [0]*W, [0]*W
for j in range(W):
    numCs[j] = getFib(j-1) * getFib(W-1-j-1)
    numLs[j] = getFib(j-2) * getFib(W-1-j-1)
    numRs[j] = getFib(j-1) * getFib(W-1-j-2)

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] * numCs[j]
        if j > 0:
            dp[i+1][j-1] += dp[i][j] * numLs[j]
        if j < W-1:
            dp[i+1][j+1] += dp[i][j] * numRs[j]
    for j in range(W):
        dp[i+1][j] %= MOD

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

pats = []
for pat in range(1<<(W-1)):
    for i in range(W-2):
        if pat & (1<<i) and pat & (1<<(i+1)):
            break
    else:
        pats.append(pat*2)

dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for pat in pats:
            L = pat & (1<<j)
            R = pat & (1<<(j+1))
            if L == 0 and R == 0:
                dp[i+1][j] += dp[i][j]
            elif L != 0 and R == 0:
                dp[i+1][j-1] += dp[i][j]
            elif L == 0 and R != 0:
                dp[i+1][j+1] += dp[i][j]
    for j in range(W):
        dp[i+1][j] %= MOD

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



def C(n, r):
    c = 1
    for i in range(1, r+1):
        c *= n
        c //= i
        n -= 1

    return c

@mt
def slv(H, W, K):
    dp = [[0] * (W+2) for _ in range(H+1)]

    
    L = [0] * (W+2)
    C = [0] * (W+2)
    R = [0] * (W+2)
    for c in product(range(2), repeat=W-1):
        for i in range(W-2):
            if c[i] * c[i+1] != 0:
                break
        else:
            for j in range(1, W+1):
                if j != 1 and c[j-2] == 1:
                    L[j] += 1
                elif j != W and c[j-1] == 1:
                    R[j] += 1
                else:
                    C[j] += 1

    dp[0][1] = 1
    mod = 10**9 + 7
    for h in range(0, H):
        for w in range(1, W+1):
            dp[h+1][w-1] += dp[h][w] * L[w]
            dp[h+1][w-1] %= mod
            dp[h+1][w] += dp[h][w] * C[w]
            dp[h+1][w] %= mod
            dp[h+1][w+1] += dp[h][w] * R[w]
            dp[h+1][w+1] %= mod


    return dp[H][K]


def main():
    H, W, K = read_int_n()
    # A = [read_int_n() for _ in range(N)]
    print(slv(H, W, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gen_pattern(curr, result):
    if len(curr) == W - 1:
        result.append(curr)
        return
    if len(curr) == 0:
        gen_pattern([0], result)
        gen_pattern([1], result)
    else:
        gen_pattern(curr + [0], result)
        if curr[-1] == 0:
            gen_pattern(curr + [1], result)
bridge = []
gen_pattern([], bridge)

MOD = 1000000007

di = []
for y in range(H + 1):
    ret = []
    for x in range(W):
        ret.append(0)
    di.append(ret)
di[0][0] = 1

for y in range(1, H + 1):
    for x in range(W):
        left = 0
        center = 0
        right = 0
        if W == 1:
            center = 1
        else:
            for b in bridge:
                if x == 0:
                    if b[x] == 0:
                        center += 1
                    if b[x] > 0:
                        right += 1
                elif x == W - 1:
                    if b[x - 1] > 0:
                        left += 1
                    if b[x - 1] == 0:
                        center += 1
                else:
                    if b[x - 1] > 0:
                        left += 1
                    if b[x - 1] == 0 and b[x] == 0:
                        center += 1
                    if b[x] > 0:
                        right += 1
        t = (di[y - 1][x] * center) % MOD
        if x > 0:
            t += (di[y - 1][x - 1] * left) % MOD
        if x < W - 1:
            t += (di[y - 1][x + 1] * right) % MOD
        di[y][x] = t % MOD

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  5 10:49:47 2019

@author: Yamazaki Kenichi
"""

H,W,K = map(int, input().split())
mod = 10**9 +7
a = [1,1,2,3,5,8,13,21]
T = [[-1 for i in range(9)] for i in range(H+1) ]
def n(h,k):
    if T[h][k] != -1:
        return T[h][k]
    res = 0
    if h == 1:
        if k == 1 or k == 2:
            T[h][k] = a[W-k]
            return a[W-k]
        else:
            T[h][k] = 0
            return 0
    res += n(h-1,k)*(a[k-1] * a[W-k])
    if k != 1:
        res += n(h-1,k-1)*(a[k-1-1] * a[W-k])
    if k != W:
        res += n(h-1,k+1)*(a[k-1] * a[W-k-1])
    T[h][k] = res
    return res % mod
ans = n(H,K)
print(ans)

Submission status: Accepted

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

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

    

for i in range(1,H+1):
    for x in range(2**(W-1)):           
        Alloc = [0]*9
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp //= 2 
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:   
            for j in range(1,9):  
                if Alloc[j-1] == 1: 
                    dp[i][j] += dp[i-1][j-1]
                elif Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007

print(dp[H][K])

Submission status: Accepted

Solution code:
H,W,K = (int(x) for x in input().split())

mat = [[0]*W for _ in range(W)]

def dfs(bar_partial):
    if len(bar_partial) == W-1:
        perm = list(range(W))
        for i,w in enumerate(bar_partial):
            if w == 1:
                perm[i] = i+1
                perm[i+1] = i
        for i in range(W):
            mat[i][perm[i]] += 1
        return
    bar_partial.append(0)
    dfs(bar_partial)
    bar_partial.pop()
    if len(bar_partial) == 0 or bar_partial[-1] == 0:
        bar_partial.append(1)
        dfs(bar_partial)
        bar_partial.pop()

dfs([])
dp_hw = [[0]*W for _ in range(H+1)]
dp_hw[0][0] = 1
for i in range(1, H+1):
    dp_prev = dp_hw[i-1]
    dp_current = dp_hw[i]
    for j in range(W):
        for k in range(W):
            dp_current[j] += dp_prev[k]*mat[j][k]
        dp_current[j] = dp_current[j] % 1000000007

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

Submission status: Accepted

Solution code:
# 縦線の数に対する横線の引き方
border_num = [1, 1, 2, 3, 5, 8, 13, 21, 34]


def noborder_both_side(cw: int, W: int) -> int:
    """縦線 cw の両隣に横線が存在しない場合の数
    """
    # (cw より左側の縦線間での横線の引き方) x (右側でのそれ)
    return border_num[cw-1] * border_num[W-cw]


def border_only_leftside(cw: int, W: int) -> int:
    """縦線 cw の左側のみに横線が存在する場合の数
    """
    # 左端にいるなら左側に横線は引けない
    if cw == 1:
        return 0

    # (cw より左側の縦線間での横線の引き方) x (右側でのそれ)
    # cw より左側は、cw と隣、隣とその隣の間の引き方は一意に決まるので、
    # それよりさらに左側の cw-2 本の縦線間での引き方を考える。
    return border_num[cw-2] * border_num[W-cw]


def border_only_rightside(cw: int, W: int) -> int:
    """縦線 cw の右側のみに縦線が存在する場合の数
    """
    # 右端にいるなら右側に横線は引けない
    if cw == W:
        return 0

    # (cw より左側の縦線間での横線の引き方) x (右側でのそれ)
    # cw より右側は、cw と隣、隣とその隣の間の引き方は一意に決まるので、
    # それよりさらに右側の W-cw-1 本の縦線間での引き方を考える。
    return border_num[cw-1] * border_num[W-cw-1]


def number_of_amidakuji(H: int, W: int, K: int) -> int:
    # 場合分けを減らすため、w 方向は余計にとってある。
    dp = [[0 for _ in range(W+2)] for _ in range(H+1)]
    dp[0][1] = 1

    for h in range(H):
        for w in range(1, W+1):
            # (h, w) -> (h+1, w) への行き方は次のように求める
            # ((h, w) への到達方法)
            # x (h+1 の横線の引き方の内 w の両隣に横線がない場合の数)
            dp[h+1][w] += dp[h][w] * noborder_both_side(w, W)

            # (h, w) -> (h+1, w-1) への行き方は次のように求める
            # ((h, w) への到達方法)
            # x (h+1 の横線の引き方の内 w の左にのみ横線がある場合の数)
            dp[h+1][w-1] += dp[h][w] * border_only_leftside(w, W)

            # (h, w) -> (h+1, w+1) への行き方は次のように求める
            # ((h, w) への到達方法)
            # x (h+1 の横線の引き方の内 w の右にのみ横線がある場合の数)
            dp[h+1][w+1] += dp[h][w] * border_only_rightside(w, W)

    return dp[H][K]


if __name__ == "__main__":
    H, W, K = map(int, input().split())
    ans = number_of_amidakuji(H, W, K)
    print(ans % 1000000007)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
INF = 10**18

H,W,K=rl()
DIV =  1000000007

rc = K-1
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0]=1
bar = [1, 1+0, 1+1, 2+1, 3+2, 5+3, 8+5, 13+8, 21+13]

for h in range(1,H+1):
    for w in range(W):
        if w != 0:
            dp[h][w] += dp[h-1][w-1]*bar[w-1]*bar[W-w-1]
        dp[h][w] += dp[h-1][w]*bar[w]*bar[W-w-1]
        if w != W-1:
            dp[h][w] += dp[h-1][w+1]*bar[w]*bar[W-w-2]

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

Submission status: Accepted

Solution code:
md = 1000000000 + 7

def fi(n):
  if n < 0:
    return 0
  elif n <= 1:
    return 1
  elif n == 2:
    return 2
  else:
    return ( fi(n-1) + fi(n-2) ) % md


h, w, k = map(int, input().split())
li = [0 for i in range(w)]

li[0] = 1

li_prev = []
li_next = []

li_prev[:] = li[:]
li_next[:] = li[:]

for j in range(h):
  for i in range(w):
    li_next[i] = (li_prev[max(0,i-1)] * fi(i-1) * fi(w-i-1)
               + li_prev[i] * fi(i) * fi(w-i-1)
               + li_prev[min(w-1,i+1)] * fi(i) * fi(w-i-2)) % md
  li_prev[:] = li_next[:]

print(li_prev[k-1])

Submission status: Accepted

Solution code:
from itertools import combinations
mod = 10**9 + 7
h, w, k = map(int, input().split())
edge = [[0]*w for i in range(w)]

for r in range(w//2+1):
    for c in combinations(range(w-1),r):
        # 横線が隣接する場合を排除
        flag = True
        if len(c) > 1:
            for i in range(len(c)-1):
                if c[i+1] - c[i] == 1:
                    flag = False
                    break
        if not flag:continue
        for i in range(w):
            if i in c: continue
            if i-1 in c:
                edge[i-1][i] += 1
                edge[i][i-1] += 1
            else:
                edge[i][i] += 1

# DP[i][j] == i行目まで見た時に1がjの位置にある場合の数
DP = [[0]*w for i in range(h+1)]
DP[0][0] = 1
for i in range(h):
    for j in range(w):
        for l in range(w):
            DP[i+1][j] = (DP[i+1][j] + DP[i][l]*edge[l][j]) % mod
#print(DP)
print(DP[-1][k-1])

Submission status: Accepted

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

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

for h in range(H):
  cnt = 0
  while cnt < (1<<(W-1)):
    if '11' not in format(cnt, 'b'):
      for w in range(W):
        if w>0 and (cnt>>(w-1)) & 1:
          dp[h+1][w-1] += dp[h][w]
        elif w<W-1 and (cnt>>w) & 1:
          dp[h+1][w+1] += dp[h][w]
        else:
          dp[h+1][w] += dp[h][w]
    cnt += 1

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