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())
if w == 1:
    print(1)
    exit()
K -= 1
mod = 1000000007
dp = [[0]*(w) for _ in range(h+1)]
for i in range(w): dp[0][0] = 1

for i in range(h):
    for j in range(1<<(w-1)):
        invalid = False
        for k in range(w-1):
            if j>>k & 1 and j>>(k+1) & 1:
                invalid = True
                break
        if invalid: continue
        used = [False]*w
        for k in range(w):
            if used[k]: continue
            if j>>k & 1:
                dp[i+1][k] = (dp[i+1][k]+dp[i][k+1])%mod
                dp[i+1][k+1] = (dp[i+1][k+1]+dp[i][k])%mod
                used[k] = True
                used[k+1] = True
            else:
                dp[i+1][k] = (dp[i+1][k]+dp[i][k])%mod
                used[k] = True
# for i in range(h+1): print(dp[i])
print(dp[h][K])

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
f=[1,1,2,3,5,8,13,21]
m=10**9+7
dp=[[1]+[0]*(w-1)for i in range(h+1)]
h=0if w==1else h
for i in range(1,h+1):
 for j in range(w):
  if j==0:dp[i][0]=(dp[i-1][0]*f[w-1] + dp[i-1][1]*f[w-2])%m;
  elif j==w-1:dp[i][w-1]=(dp[i-1][w-1]*f[w-1] + dp[i-1][w-2]*f[w-2])%m
  else:dp[i][j]=(dp[i-1][j]*f[j]*f[w-j-1]+dp[i-1][j-1]*f[j-1]*f[w-j-1]+dp[i-1][j+1]*f[j]*f[w-j-2])%m
print(dp[h][k-1])

Submission status: Accepted

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

fdp = [[0, 0] for _ in range(w)]
fdp[0][0] = 1
for i in range(w - 1):
    fdp[i+1][0] += fdp[i][0]
    fdp[i+1][1] += fdp[i][0]
    fdp[i+1][0] += fdp[i][1]

def f(i):
    if i < 0:
        return 1
    return fdp[i][0] + fdp[i][1]

for _ in range(h):
    ndp = [0] * w
    for i in range(w):
        ndp[i] = (ndp[i] + dp[i] * f(i - 1) * f(w - i - 2))  % MOD
        if i + 1 < w:
            ndp[i+1] = (ndp[i+1] + dp[i] * f(i - 1) * f(w - i - 3)) % MOD
        if i - 1 >= 0:
            ndp[i-1] = (ndp[i-1] + dp[i] * f(i - 2) * f(w - i - 2)) % MOD
    dp = ndp
print(dp[k-1])

Submission status: Accepted

Solution code:
def resolve():
    H, W, K = list(map(int, input().split()))
    dp = [[0 for _ in range(W)] for __ in range(H+1)]
    dp[0][0] = 1
    mod = 10**9+7
    for h in range(H):
        for w in range(W):
            downleft = 0
            down = 0
            downright = 0
            for bits in range(1<<W-1):
                invalid = False
                for odr in range(W-2):
                    if (bits & (1<<odr)) and (bits & (1<<(odr+1))):
                        invalid = True
                if invalid:
                    continue
                if w > 0 and (bits & (1<<(w-1))):
                    downleft += 1
                elif w < W-1 and (bits & (1<<w)):
                    downright += 1
                else:
                    down += 1
            if w > 0 and downleft > 0:
                dp[h+1][w-1] += downleft*dp[h][w]
                dp[h+1][w-1] %= mod 
            if w < W-1 and downright > 0:
                dp[h+1][w+1] += downright*dp[h][w]
                dp[h+1][w+1] %= mod
            if down > 0:
                dp[h+1][w] += down*dp[h][w]
                dp[h+1][w] %= mod
    print(dp[H][K-1])


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys

def S(): return sys.stdin.readline().rstrip()

H,W,K = map(int,S().split())
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行目にjに達する横線の引き方

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

print(dp[H][K])

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc113
# 12:01-12:49 give up -> kaisetsu
# 11:57-12:25 try again

# from pprint import pprint as ppr


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

#     v = "v"
#     h = "h"
#     dp = [[{"v": 0, "h": 0} for _ in range(W)] for _ in range(H)]
#     dp[0][0][v] = 1

#     for i in range(H):

#         for j in range(W):
#             # horizontal computation
#             if j == 0:
#                 dp[i][j+1][h] += dp[i][j][v]
#             elif j == W-1:
#                 dp[i][j-1][h] += dp[i][j][v]
#             else:
#                 dp[i][j+1][h] += dp[i][j][v]
#                 dp[i][j-1][h] += dp[i][j][v]

#         if i < H-1:
#             for j in range(W):
#                 # vertical computation
#                 dp[i+1][j][v] += dp[i][j][v] + dp[i][j][h]
    
#     ppr(dp)

#     return dp[H-1][K-1][v] + dp[H-1][K-1][h]


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

    if W == 1:
        return 1

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

    bridges_list = []

    def preset(i, bridges, n_cand):
        if i == n_cand:
            bridges_list.append(bridges)
            return None

        if i-1 in bridges:
            preset(i+1, bridges, n_cand)
        else:
            bridges_1 = bridges[:]
            bridges_2 = bridges[:]
            bridges_1.append(i)

            preset(i+1, bridges_1, n_cand)
            preset(i+1, bridges_2, n_cand)

    preset(0, [], W-1)

    n_bridges = [0] * (W-1)
    for bridges in bridges_list:
        for x in bridges:
            n_bridges[x] += 1

    n_all_cands = len(bridges_list)

    # ppr(bridges_list)
    # ppr(n_bridges)

    dp[0][0] = (n_all_cands-n_bridges[0])
    dp[0][1] = n_bridges[0]

    for i in range(H-1):
        for j in range(W):
            if j == 0:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j])
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
            elif j == W-1:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
            else:
                dp[i+1][j] += dp[i][j] * (n_all_cands-n_bridges[j-1]-n_bridges[j])
                dp[i+1][j-1] += dp[i][j] * n_bridges[j-1]
                dp[i+1][j+1] += dp[i][j] * n_bridges[j]
    # ppr(dp)

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


print(main())

Submission status: Accepted

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

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

dp = [ [0]*w for _ in range(h+1) ]
dp[0][0] = 1
for i in range(1,h+1):
    for wi in range(w):
        dp[i][wi] = dp[i-1][wi] * patterns[w-1-wi] * patterns[wi-0]
        if wi > 0:
            dp[i][wi] += dp[i-1][wi-1] * patterns[w-1-wi] * patterns[wi-1]
        if wi < w-1:
            dp[i][wi] += dp[i-1][wi+1] * patterns[w-1-wi-1] * patterns[wi-0]
        dp[i][wi] %= MOD

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

Submission status: Accepted

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    sys.setrecursionlimit(10**9)
    h,w,k=map(int,input().split())
    dp=[0]*w
    dp[k-1]=1
    ne=[0]*w
    mod=10**9+7
    table=[1,1,2,3,5,8,13,21,34]
    for c in range(h):
        for i in range(w):
            ne[i]=dp[i]*table[i]*table[w-i-1]
            if i>0:
                ne[i]+=dp[i-1]*table[i-1]*table[w-i-1]
            if i<w-1:
                ne[i]+=dp[i+1]*table[i]*table[w-i-2]
            ne[i]%=mod
        dp,ne=ne,dp
    print(dp[0])


if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

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

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

    que = deque("0")
    com = {i: {j: 0 for j in (-1, 0, 1)} for i in range(1, w + 1)}

    while que:
        cur = que.popleft()

        if len(cur) == w:
            cur += "0"
            for col in range(1, w + 1):
                if col >= 2 and cur[col - 1] == "1":
                    com[col][-1] += 1
                if col <= w - 1 and cur[col] == "1":
                    com[col][1] += 1
                if cur[col-1] == cur[col] == "0":
                    com[col][0] += 1
        else:
            if cur[-1] == "0":
                que.append(cur + "1")
            que.append(cur + "0")

    dp = [[0] * (w + 1) for _ in range(h + 1)]
    dp[0][1] = 1
    for row in range(h):
        for col in range(1, w + 1):
            if col >= 2:
                dp[row + 1][col - 1] += dp[row][col] * com[col][-1]
                dp[row + 1][col - 1] %= MOD
            if col <= w - 1:
                dp[row + 1][col + 1] += dp[row][col] * com[col][1]
                dp[row + 1][col + 1] %= MOD
            dp[row + 1][col] += dp[row][col] * com[col][0]
            dp[row + 1][col] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


for h in range(H):
    for i in range(2 ** (W-1)):
        if '11' in bin(i):
            continue
        for w in range(W):  # このループが一番のポイント
            if w == 0:
                if (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            elif 1 <= w < W-1:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                elif (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            else:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                else:
                    dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= MOD

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

Submission status: Accepted

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

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

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


for h in range(H):
    for i in range(2 ** (W-1)):
        if '11' in bin(i):
            continue
        for w in range(W):  # このループが一番のポイント
            if w == 0:
                if (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            elif 1 <= w < W-1:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                elif (i >> w) & 1:
                    dp[h+1][w] += dp[h][w+1]
                else:
                    dp[h+1][w] += dp[h][w]
            else:
                if (i >> (w-1)) & 1:
                    dp[h+1][w] += dp[h][w-1]
                else:
                    dp[h+1][w] += dp[h][w]
            dp[h+1][w] %= MOD

# print(*dp, sep='\n')

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [[0]*w for _ in range(h+1)] # 横棒i本のときの0->jに至るくじ

dp[0][0] = 1

d = {}
M = 10**9+7
def sub(i):
    # i本棒がある区間の横棒の入れ方
    if i in d:
        return d[i]
    if i<=1:
        ans = 1
    else:
        ans = sub(i-1) + sub(i-2)
    ans %= M
    d[i] = ans
    return ans
    

for i in range(1,h+1):
    for j in range(w):
        if j>=1:
            dp[i][j] += dp[i-1][j-1]*sub(j-1)*sub(w-j-1)
        if j<=w-2:
            dp[i][j] += dp[i-1][j+1]*sub(j)*sub(w-j-2)
        dp[i][j] += dp[i-1][j]*sub(j)*sub(w-j-1)
        dp[i][j] %= M
print(dp[h][k])

Submission status: Accepted

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

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for bit in range(1<<(W-1)):
        if "11" in bin(bit): continue
        for w in range(W):
            if w > 0 and (bit>>(w-1))&1:
                dp[h+1][w-1] += dp[h][w]
                dp[h+1][w-1] %= MOD
            elif (bit>>w)&1:
                dp[h+1][w+1] += dp[h][w]
                dp[h+1][w+1] %= MOD
            else:
                dp[h+1][w] += dp[h][w]
                dp[h+1][w] %= MOD

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

Submission status: Accepted

Solution code:
def split(word): 
    return [char for char in word] 
MOD=10**9+7
h,w,k1=map(int,input().split())
dp=[]
for i in range(h+1):
  dp.append([])
  for j in range(w):
    dp[-1].append(0)
dp[0][0]=1
connections=[0]*(w-1)
totallegal=0
for i in range(pow(2,w-1)):
  s='{0:b}'.format(i)
  k=split(s)
  k.reverse()
  for j in range(w-1-len(k)):
    k.append('0')
  k.reverse()
  failflag=0
  for j in range(1,w-1):
    if k[j]=='1' and k[j-1]=='1':
      failflag=1
  if failflag==1:
    continue
  for j in range(w-1):
    if k[j]=='1':
      connections[j]+=1
  totallegal+=1
for i in range(h):
  for j in range(w):
    used=0
    if j>0:
      dp[i+1][j-1]=(dp[i+1][j-1]+connections[j-1]*dp[i][j])%MOD
      used+=connections[j-1]
    if j<w-1:
      dp[i+1][j+1]=(dp[i+1][j+1]+connections[j]*dp[i][j])%MOD
      used+=connections[j]
    dp[i+1][j]=(dp[i+1][j]+(totallegal-used)*dp[i][j])%MOD
print(dp[h][k1-1])

Submission status: Accepted

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

mod = 10 ** 9 + 7

def dfs(idx, used):
    if idx == w - 1:
        return [[]]

    ret = dfs(idx + 1, False)
    if used == False:
        ret2 = dfs(idx + 1, True)
        for l in ret2:
            ret.append(l + [idx])
    return ret

combs = dfs(0, 0)

dp = [0] * w
dp[0] = 1
for i in range(h):
    dp_new = [0] * w
    for bars in combs:
        used = set()
        for start in bars:
            dp_new[start] += dp[start + 1]
            dp_new[start + 1] += dp[start]

            used.add(start)
            used.add(start + 1)

        for i in range(w):
            if i not in used:
                dp_new[i] += dp[i]

    dp = [x % mod for x in dp_new]

print(dp[k-1])

Submission status: Accepted

Solution code:
# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

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

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

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

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
    res *= P[(W - 1) - (R + 1)]
    res %= DIV
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
    # 左に移動する
    if j - 1 >= 0:
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
    # 何もしない
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1] % DIV)

Submission status: Accepted

Solution code:
# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

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

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

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

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
#  print("calc L",L,"R",R)
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
#    print("P[L - 2]",P[L - 2],"res",res)
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
#    print(min((W - 1) - (R + 1),len(P)))
    res *= P[(W - 1) - (R + 1)]
#    print("P[(W - 1) - (R + 1)]",min((W - 1) - (R + 1),len(P)),"res",res)
    res %= DIV
#  print(res,"通り")
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
    # 左に移動する
    if j - 1 >= 0:
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
    # 何もしない
#    print("i",i,"j",j,"からi",i,"j",j,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
#    print("i",i,"j",j,"からi",i,"j",j,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
#  for d in dp:
#    print(dp)

    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1] % DIV)

Submission status: Accepted

Solution code:
def check(amidakuji,w):
    before=0
    flag=True
    for _ in range(w-1):
        if amidakuji&1==1 and before==1:
            flag=False
            break
        elif amidakuji&1==1:
            before=1
            amidakuji>>=1
        else:
            before=0
            amidakuji>>=1
    return flag

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    h,w,k=map(int,readline().split())

    dp=[[0]*w for _ in range(h+1)]
    dp[0][0]=1
    for i in range(1,h+1):
        for bit in range(1<<(w-1)):
            if check(bit,w)==False:
                continue
            else:
                for j in range(w):
                    if j==0:
                        if bit&1==1:
                            dp[i][j+1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    elif j==w-1:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                        else:
                            dp[i][j]+=dp[i-1][j]
                    else:
                        if bit&1==1:
                            dp[i][j-1]+=dp[i-1][j]
                            bit>>=1
                        else:
                            bit>>=1
                            if bit&1==1:
                                dp[i][j+1]+=dp[i-1][j]
                            else:
                                dp[i][j]+=dp[i-1][j]

                for j in range(w):
                    dp[i][j]%=mod

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

    bf = [0] * (w + 2)
    nx = [0] * (w + 2)
    bf[1] = 1

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

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            nx[j] = c[j - 1] * c[w - j] * bf[j] + c[j - 1] * c[w - j - 1] * bf[j + 1] + c[j - 2] * c[w - j] * bf[j - 1]

        bf = nx
        nx = [0] * (w + 2)

    print(bf[k] % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fib():
    a = 1
    b = 0
    while 1:
        c = a + b
        yield c
        a = b
        b = c


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

    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    f = fib()
    c = [f.__next__() for _ in range(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            dp[i][j] = c[j - 1] * c[w - j] * dp[i - 1][j] + c[j - 1] * c[w - j - 1] * dp[i - 1][j + 1] + c[j - 2] * c[w - j] * dp[i - 1][j - 1]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fib(n):
    a = 1
    b = 0
    i = 0
    while i < n:
        i += 1
        c = a + b
        yield c
        a = b
        b = c


def main():
    h, w, k = map(int, input().split())
    mod = 10 ** 9 + 7
    
    dp = [[0] * (w + 2) for _ in range(h + 1)]
    dp[0][1] = 1
    c = [i for i in fib(w + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            x = c[j - 1] * c[w - j]
            y = c[j - 1] * c[w - j - 1]
            z = c[j - 2] * c[w - j]

            dp[i][j] = (x * dp[i - 1][j] + y * dp[i - 1][j + 1] + z * dp[i - 1][j - 1]) % mod

    print(dp[h][k])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10**9+7

num = 2**(w-1)

li = []

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

for i in range(num):
    tmp = format(i, '0'+str(w-1)+'b')
    cnt = 0
    for j in range(w-1):
        if tmp[j] == '1':
            if cnt == 1:
                break
            else:
                cnt = 1
        else:
            cnt = 0
        if j == w-2:
            li.append(tmp)
    #print(tmp)

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

dp[0][0] = 1

for i in range(h):
    #print(i)
    for j in range(len(li)):
        for k in range(w):
            #print(li[j],li[j][0] == '1')
            if k == 0:
                if li[j][k] == '1':
                    dp[i+1][k+1] += dp[i][k]
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            elif k == w-1:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            else:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                elif li[j][k] == '1':
                    #print(dp[i][k],i,k,i+1,k+1)
                    dp[i+1][k+1] += dp[i][k]
                    #print(dp[i+1][k+1],dp)
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
                    
print(dp[h][K-1])

Submission status: Accepted

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

mod = 10**9 + 7
   

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

for i in range(h):
    for bit in range(1<<(w-1)):
        if '11' in bin(bit) : continue
        for j in range(w):
            if j > 0 and bit & (1 << (j-1)):
                dp[i+1][j-1] += dp[i][j] % mod 
            elif bit & (1 << j):
                dp[i+1][j+1] += dp[i][j] % mod
            else:
                dp[i+1][j] += dp[i][j] % mod
                
print(dp[h][k-1]%mod)

Submission status: Accepted

Solution code:


"""
AtCoder Beginner Contest 113  D - Number of Amidakuji

愚直に考えると、
・それぞれの縦棒の間に、横棒があるかないかの2通り。これがある高さhだけで、2^(W-1)通りある（横棒が２連続で続かないので、厳密には違うが）。
・これが高さH（最大100個分）あるので、(2^7)^100 とか？とにかく全探索は間に合わない。

メタ視点だが、W<=8なので、bitDPとかやれそう。
愚直解の何がよくないかというと、たとえば H = 6,W = 4 みたいなあみだくじについて考えるとして、
・この中で上から3段目までが同じでそれより下が異なるあみだくじというのがあるが、同じ部分も毎回シミュレートしてしまうのが重複計算になって無駄。

なので、高さごとに取りうる横棒のパターンを確認して、それらについて移動先の場合の数を求めていけばいいか。

各高さについて毎回横棒のパターンをbitで探索するが何故か思いつかなかった。
"""

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


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

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        # 高さi、左からj本目の縦棒にいるとき、どう移動するか。
        for j in range(W):
          

            # 右に移る棒がある時に、右に行ってから下へ移動する場合
            if j != W-1 and bit & (1 << (W-2-j)): # j=0 の時に左端に1が立っているか確認したい、
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            # 左に移る棒があるときに、左に行ってから下へ移動する場合
            elif j != 0 and bit & (1 << (W-1-j)): # j=W-1 のときに、右端に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(i,bin(bit),j,dp)



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

Submission status: Accepted

Solution code:

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


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

ws = set()
for bit in range(1 << (W-1)):
    if "11" in bin(bit):
        continue
    ws.add(bit)


for i in range(H):
    for bit in ws:
        # 高さi、左からj本目の縦棒にいるとき、どう移動するか。
        for j in range(W):
          

            # 右に移る棒がある時に、右に行ってから下へ移動する場合
            if j != W-1 and bit & (1 << (W-2-j)): # j=0 の時に左端に1が立っているか確認したい、
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD

            # 左に移る棒があるときに、左に行ってから下へ移動する場合
            elif j != 0 and bit & (1 << (W-1-j)): # j=W-1 のときに、右端に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(i,bin(bit),j,dp)



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

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

mod = 10**9+7

# 左(あるいは右)にn本の縦棒があり、真横と繋がっている時の場合の数
j = [0,1,1,2,3,5,8,13];
# 左(あるいは右)にn本の縦棒があり、真横と繋がっていない時の場合の数
m = [1,1,2,3,5,8,13,21];
 
# dp[h][w] : h行目を終えた時点でwにいる場合の数
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
 
for h in range(H+1):
    for w in range(W):
        # 右に移動
        if w != 0:
            dp[h][w] += dp[h-1][w-1] * j[w] * m[W-1-w]
        # 左に移動
        if w != W-1:
            dp[h][w] += dp[h-1][w+1] * m[w] * j[W-1-w]
        # 真下に移動
        dp[h][w] += dp[h-1][w] * m[w] * m[W-1-w]
        
        dp[h][w] %= mod;

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

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
def two(x):
	return "0"*(w-1-len(bin(x)[2:]))+bin(x)[2:]
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
	for j in range(2**(w-1)):
		r=two(j)
		f=1
		for k in range(w-2):
			if r[k]==r[k+1]=="1":
				f=0
				break
		if f:
			for k in range(w):
				if k+1<w:
					if r[k]=="1":
						dp[i+1][k+1]+=dp[i][k]
						dp[i+1][k+1]%=mod
						continue
				if k>0:
					if r[k-1]=="1":
						dp[i+1][k-1]+=dp[i][k]
						dp[i+1][k-1]%=mod
						continue
				dp[i+1][k]+=dp[i][k]
				dp[i+1][k]%=mod
print(dp[h][K-1])

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
mod = 10**9+7
patterns = []
for p in itertools.product([0, 1], repeat=W-1):
    valid = True
    for i in range(W-2):
        if p[i] == p[i+1] == 1:
            valid = False
            break
    if valid:
        patterns += [p]

dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for pattern in patterns:
            if j > 0 and pattern[j-1] == 1:
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= mod
            elif j < W-1 and pattern[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])