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:
import sys
h, w, k = map(int, input().split())

mod = 10 ** 9 + 7

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

n_join = [0 for i in range(w-1)]
n_unjoin = [0 for i in range(w-1)]
cnt = 0

for i in range(2 ** (w-1)):
    p = 0
    f = 1
    tmp_join = []
    tmp_unjoin = []
    for j in range(w-1):
        c = i & (1 << j)
        if c:
            tmp_join.append(j)
        if not (c or p):
            tmp_unjoin.append(j)
        if p and c:
            f = 0
            break
        p = c
    if f:
        cnt += 1
        for j in tmp_join:
            n_join[j] += 1
        for j in tmp_unjoin:
            n_unjoin[j] += 1

n_unjoin.append(cnt - n_join[-1])

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

for i in range(1,h):
    for j in range(w):
        dp[i][j] += dp[i-1][j] * n_unjoin[j] % mod
        dp[i][j] %= mod
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * n_join[j-1] % mod
            dp[i][j] %= mod
        if j < w - 1:
            dp[i][j] += dp[i-1][j+1] * n_join[j] % mod
            dp[i][j] %= mod
        
print(dp[h-1][k-1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

H,W,K = LI()

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

good = []
for ami in range(2**(W-1)):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

H,W,K = LI()

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

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

good = []
for ami in range(2**(W-1)-1):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Submission status: Accepted

Solution code:
w = [1, 2]
for i in range(6):
    w.append(w[-2] + w[-1])
H, W, K = map(int,input().split())
mod = 10 ** 9 + 7
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 >= 1:
            k = 1
            if j - 2 >= 0:
                k *= w[j - 2]
            if W - j - 2 >= 0:
                k *= w[W - j - 2]
            dp[i+1][j-1] += k * dp[i][j]
            dp[i+1][j-1] %= mod
        k = 1
        if j - 1 >= 0:
            k *= w[j - 1]
        if  W - j - 2 >= 0:
            k *= w[W - j - 2]
        dp[i+1][j] += k * dp[i][j]
        dp[i+1][j] %= mod
        if j <= W - 2:
            k = 1
            if j - 1 >= 0:
                k *= w[j - 1]
            if W - j - 3 >= 0:
                k *= w[W - j - 3]
            dp[i+1][j+1] += k * dp[i][j]
            dp[i+1][j+1] %= mod

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

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)):
            # 横同士の繋がり
            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)
l=[1,1,2,3,5,8,13,21,34]#n本の縦線に高さ1のvalidな横棒を引く通り、フィボナッチ数列になる
#a_n:=n本の縦線にvalidな横棒を引く通りの総数、とすれば
#n+1本の時は1.1と2本目に横棒を引く（2と3の間に引けないのでa_n-1通り）
#          2.                引かない（a_n通り）
#よって漸化式a_n+1=a_n+a_n-1が成立。
dp[0]=1
mod=10**9+7
r=[0]*w
for i in range(h):
    for i in range(w):
        r[i]=dp[i]*l[i]*l[w-1-i]#左右に横棒を引かない
        if i>=1:
            r[i]+=dp[i-1]*l[i-1]*l[w-1-i]#左にのみ横棒を引く
        if i<=w-2:
            r[i]+=dp[i+1]*l[i]*l[w-2-i]#右にのみ横棒を引く
        r[i]%=mod
    dp,r=r,dp

print(dp[k-1])

Submission status: Accepted

Solution code:
'''Yoshichiの日記
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。
現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、
                   次の隣へも線が引かれている状態)
'''
from collections import defaultdict
h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))
def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]
    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Submission status: Accepted

Solution code:
'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)）
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ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)) #高さH（一番下）、K-1番目の棒を調べる

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
H, W, K = lr()
cases = [1] * 10  # 縦棒i本で何通りの横棒の書き方があるか(0本含む)
cases[-1] = 0 
for i in range(2, 9):
    cases[i] = cases[i-2] + cases[i-1]

dp = [0] * W
dp[0] = 1
for i in range(H):
    prev = dp[:]
    for j in range(W):
        left = j; right = W-(j+1)
        dp[j] *= cases[left] * cases[right]
        if j > 0:
            dp[j] += prev[j-1] * cases[left-1] * cases[right]
        if j < W-1:
            dp[j] += prev[j+1] * cases[left] * cases[right-1]
        dp[j] %= MOD
        
answer = dp[K-1] % MOD
print(answer)
# 19

Submission status: Accepted

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

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

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

l = [[0]*3 for i in range(w)]

for i in range(2**(w-1)):
    if "11" in bin(i):
        continue

    for j in range(w-1):
        if (i >> j) & 1:        
            l[j][2] += 1
            l[j+1][0] += 1

fib = [1,1]
for i in range(10):
    fib.append(fib[-1]+fib[-2])
for i in l:
    i[1] = fib[w] - sum(i)

for i in range(h):
    for j in range(w):
        dp[i+1][j] += dp[i][j]*l[j][1]%mod
        if j != 0:
            dp[i+1][j] += dp[i][j-1]*l[j][0]%mod
        if j != w-1:
            dp[i+1][j] += dp[i][j+1]*l[j][2]%mod
        dp[i+1][j] %= mod

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

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
mod=10**9+7
dp=[[0 for i in range(w)] for j in range(h+1)]
for i in range(2**(w-1)):dp[0][0]=1
for i in range(1,h+1):
    for j in range(2**(w-1)):
        s=format(j,"b").zfill(w-1)
        if "11" in s:continue
        exchanged=[False]*w
        for k in range(w-1):
            if s[k]=="1":
                dp[i][k]+=dp[i-1][k+1]
                dp[i][k+1]+=dp[i-1][k]
                dp[i][k]%=mod
                dp[i][k+1]%=mod
                exchanged[k]=True
                exchanged[k+1]=True
        for k in range(w):
            if exchanged[k]:continue
            dp[i][k]+=dp[i-1][k]
            dp[i][k]%=mod

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    dp = [[0] * W for _ in range(H + 1)]
    dp[0][0] = 1
    # 横線[0,H)
    # H->終着点

    for h in range(H):
        for bit in range(1 << (W - 1)):
            if '11' in bin(bit): continue
            toes = list(range(W))
            for j in range(W - 1):
                if (bit >> j) & 1:
                    toes[j], toes[j + 1] = toes[j + 1], toes[j]
            for frm, to in enumerate(toes):
                dp[h + 1][to] = (dp[h + 1][to] + dp[h][frm]) % MOD
    ans = dp[H][K - 1]
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
p = 10**9+7
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
F = [1, 2, 3, 5, 8, 13, 21][:w]+[1]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-2]*F[w-2-j]
        b = DP[i][j]*F[j-1]*F[w-2-j]
        c = DP[i][j+1]*F[j-1]*F[w-3-j]
        DP[i+1][j] = (a+b+c) % p
print(DP[h][k-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
H, W, K = map(int,input().split())
dp = [[0 for k in range(W)] for l in range(H+1)]
dp[0][0] = 1
A = []  # ありうる横棒のリスト
for b in range(2**(W-1)):
    if "11" not in bin(b):
        A.append(bin(b)[2:].zfill(W-1))

for k in range(H):
    for e in A:
        for i in range(W):
            if i < W-1 and e[i] == "1": # 右に行くパターン
                dp[k+1][i+1] += dp[k][i]
                dp[k+1][i+1] %= MOD
            elif i >= 1 and e[i-1] == "1": # 左に行くパターン
                dp[k+1][i-1] += dp[k][i]
                dp[k+1][i-1] %= MOD
            else:
                dp[k+1][i] += dp[k][i]
                dp[k+1][i] %= MOD

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

Submission status: Accepted

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

move = [[0 for i in range(w)] for j in range(w)]
from itertools import product
for bits in product([0, 1], repeat=w-1):
    flag = True
    for i in range(w-2):
        if bits[i] == 1 and bits[i+1] == 1:
            flag = False
    if not flag:
        continue

    for i in range(w):
        a = 0
        if i != 0:
            if bits[i-1] == 1:
                move[i][i-1] += 1
                a = 1
        if i != w-1:
            if bits[i] == 1:
                move[i][i+1] += 1
                a = 1
        if a == 0:
            move[i][i] += 1

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

dp[0][0] = 1
MOD = 10**9 + 7

for i in range(h):
    for j in range(w):
        for k1 in range(w):
            dp[i+1][k1] += dp[i][j] * move[j][k1]
            dp[i+1][k1] %= MOD


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

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
p = 10**9+7
# DP[i][j]=i段目まで見て0からjに着くパターン数
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
# F[k]=k個の枠に隣り合わないように線を引くパターンの数
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-1]*F[w-1-j]
        b = DP[i][j]*F[j]*F[w-1-j]
        c = DP[i][j+1]*F[j]*F[w-2-j]
        DP[i+1][j] = (a+b+c) % p
print(DP[h][k-1])

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
# h, w, k = 15, 8, 5
# h, w, k = 2, 3, 1
# h, w, k = 2, 3, 3
# h, w, k = 1, 3, 2
p = 10**9+7
# DP[i][j]=i段目まで見て0からjに着くパターン数
# 最終的にDP[h][k-1]を求める
DP = [[0 for j in range(w+1)] for i in range(h+1)]
DP[0][0] = 1
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(h):
    for j in range(w):
        a = DP[i][j-1]*F[j-1]*F[w-1-j]
        b = DP[i][j+1]*F[j]*F[w-2-j]
        c = DP[i][j]*F[j]*F[w-1-j]
        DP[i+1][j] = (a+b+c) % p
print(DP[h][k-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W for _ in range(H + 1)]  # 数え上げ問題なので0で初期化する
    dp[0][0] = 1  # 初期条件
    for h in range(H):
        for bit in range(1 << (W - 1)):  # 左ビットシフトで2 ** (W-1)と同じ
            if '11' in bin(bit): continue  # ある頂点から左右方向に棒が伸びているケースはスルー
            for w in range(W):
                # w番目の棒を考える
                if w and bit & (1 << (w - 1)):  # leftを見るので1<<w-1と確認, w=0の時はleftにいけないことに注意する
                    dp[h + 1][w - 1] += dp[h][w] % MOD
                elif bit & (1 << w):  # rightを見るので1<<w確認
                    dp[h + 1][w + 1] += dp[h][w] % MOD
                else:  # down, 左右どちらにもいかない時
                    dp[h + 1][w] += dp[h][w] % MOD
    # for i in dp:
    #     print(*i)
    print(dp[H][K - 1] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

MOD = 10 ** 9 + 7

states = [0]
for state in range(1, 1 << (W - 1)):
    flag = True
    for j in range(1, W - 1):
        if ((state >> j - 1) & 1) and ((state >> j) & 1):
            flag = False
    if flag: states.append(state)

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

dp[0][0] = 1

# 貰うDP
for i in range(H):
    for state in states:
        for j in range(W - 1):
            if (state >> j) & 1:
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j + 1]) % MOD
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD
            else:
                if j == 0:
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
                elif not ((state >> j - 1) & 1):
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
                if j == W - 2:
                    dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j + 1]) % MOD

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

Submission status: Accepted

Solution code:
"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] O(100*8)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもO(7*7*7))
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] O(100*8)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもO(7*7*3))
    o(10**6)には入りそう
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
    dp[h][w]: h番目のrow(h: 0~H(終着))で棒w(w: 0~W-1)にいる状態になるための横線(0~h)の組合せ数
    dp[h][w] = A*dp[h-1][w-1] + B*dp[h-1][w] + C*dp[h-1][w+1] o(1000)
    A, B, Cはなんかうまいこと決めれそう。(全探索でもmax7*7*3通り)o(1000) 
    どうやってもO(10**6)には入りそう
    """
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    dp = [[0]*W for _ in range(H+1)]
    dp[0][0] = 1
    for h in range(1, H+1):
        for w in range(W):
            A, B, C = 0, 0, 0
            for i in range(2 ** (W-1)):
                lines = []
                for j in range(W-1):
                    if ((i >> j) & 1):
                        if lines and lines[-1]:
                            break
                        lines.append(True)
                    else:
                        lines.append(False)
                else:
                    if w-1 >= 0 and lines[w-1]:
                        A += 1
                    elif w <= W-2 and lines[w]:
                        C += 1
                    else:
                        B += 1
            if w-1 >= 0:
                dp[h][w] += dp[h-1][w-1] * A
            dp[h][w] += dp[h-1][w] * B
            if w+1 <= W-1:
                dp[h][w] += dp[h-1][w+1] * C
    print(dp[H][K-1] % (10**9+7))
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w, k = map(int, readline().split())
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(h):
    for b in range(1 << (w - 1)):
        if '11' in bin(b):
            continue
        for j in range(w):
            if j and b & (1 << (j - 1)):
                dp[i + 1][j - 1] += dp[i][j]
            elif b & (1 << j):
                dp[i + 1][j + 1] += dp[i][j]
            else:
                dp[i + 1][j] += dp[i][j]
print(dp[-1][k - 1] % mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc113/tasks/abc113_d
# おっこの間やったばかり

H, W, K = read_ints()
if W == 1:
    print(1)
    exit()  # コーナーケース
# DP
# dp[h][k] ... 0からスタートしたときに,[0,h)の横線まで考慮して、k番目に到達できる通りの総数
# 繊維は2**8を全探索 ただし、条件を満たさないやつは注意する


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


# swapする要素のidxのペアを返す
def check_valid(p):
    # 1が連続してはいけない
    for pp, ppp in zip(p, p[1:]):
        if pp == 1 and ppp == 1:
            return False
    return True


def generate_ij_to_swap():
    ret = []
    for p in product(range(2), repeat=W - 1):
        if not check_valid(p):
            continue
        pre = False
        for i, pp in enu(p):
            if pp:
                ret.append((i, i + 1))
                ret.append((i + 1, i))
            elif pre == 0 and pp == 0:
                ret.append((i, i))  # つながってないやつ
            pre = pp
        if pre == 0:
            ret.append((i + 1, i + 1))
    return ret


swap_idx = generate_ij_to_swap()


for h in ra(H):
    for i, j in swap_idx:
        dp[h + 1][j] += dp[h][i] % MOD  # 遷移の更新

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

Submission status: Accepted

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

f = [0]*(W+1)
f[0] = 1
f[1] = 2
for i in range(2,W+1):
    f[i] = f[i-1] + f[i-2]

dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][K] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] += (dp[i-1][j] * f[max(0,j-2)] * f[max(0,W-j-1)]
                     + dp[i-1][j-1] * f[max(0,j-3)] * f[max(0,W-j-1)]
                     + dp[i-1][j+1] * f[max(0,j-2)] * f[max(0,W-j-2)] )
        dp[i][j] %= mod
print(dp[-1][1])

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(H):
    for b in range(1<<(W-1)):
        if '11' in bin(b): continue
        for k in range(W):
            if k and b&(1<<(k-1)):
                dp[i+1][k-1] += dp[i][k]
            elif b&(1<<k):
                dp[i+1][k+1] += dp[i][k]
            else:
                dp[i+1][k] += dp[i][k]
print(dp[-1][K-1] % MOD)

Submission status: Accepted

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

MOD = 10**9+7
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

def comb(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % MOD
        q = q * (i+1) % MOD
    return p * pow(q, MOD-2, MOD) % MOD

p = [1]*(8+1)
p[1] = 2
p[2] = 3
for i in range(3,W+1):
    p[i] = p[i-1] + p[i-2]

def f(x):
    if x < 1: return 1
    return p[x]

dp = [[Mint() for _ in range(W+2)] for __ in range(H+1)]
dp[0][K] += 1
for r in range(H):
    for c in range(1, W+1):
        if c >= 2:
            dp[r+1][c-1] += dp[r][c] * (f(c-3) * f(W-c-1))
        dp[r+1][c] += dp[r][c] * (f(c-2) * f(W-c-1))
        if c <= W-1:
            dp[r+1][c+1] += dp[r][c] * (f(c-2) * f(W-c-2))
print(dp[H][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 b in range(1<<(W-1)):
        if '11' in bin(b): continue
        for k in range(W):
            if k and b&(1<<(k-1)):
                dp[i+1][k-1] += dp[i][k]
            elif b&(1<<k):
                dp[i+1][k+1] += dp[i][k]
            else:
                dp[i+1][k] += dp[i][k]

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w,k = LI()
    dp = [[0]*w for _ in range(h+1)]
    dp[0][0] = 1
    k -= 1
    f = [1,1]
    for i in range(w):
        f.append(f[-1]+f[-2])

    for i in range(h):
        ni = i+1
        for j in range(w):
            dpj = dp[i][j]
            nj = j+1
            if nj < w:
                l = f[j]
                r = f[w-1-nj]
                dp[ni][nj] += l*r*dpj%mod
            l = f[j]
            r = f[w-1-j]
            dp[ni][j] += l*r*dpj%mod
            nj = j-1
            if nj >= 0:
                l = f[nj]
                r = f[w-1-j]
                dp[ni][nj] += l*r*dpj%mod
    print(dp[h][k]%mod)
    return

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

Submission status: Accepted

Solution code:
import sys
mod = 7 + 10 ** 9

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    DP = [[0] * W for _ in range(H + 1)]
    pattern = [1, 2, 3, 5, 8, 13, 21]
    DP[0][0] = 1
    for h in range(H):
        for w in range(W):
            if w == 0:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w+1] * pattern[max(0, W - 3)]) % mod
            elif w == W - 1:
                DP[h+1][w] += (DP[h][w] * pattern[max(0, W - 2)]) % mod
                if W > 1: DP[h+1][w] += (DP[h][w-1] * pattern[max(0, W - 3)]) % mod
            else:
                DP[h+1][w] += (DP[h][w]  * pattern[max(0, w - 1)] * pattern[max(0, W - w - 2)]) % mod
                DP[h+1][w] += (DP[h][w+1] * pattern[max(0, w - 1)] * pattern[max(0, W - w - 3)]) % mod
                DP[h+1][w] += (DP[h][w-1] * pattern[max(0, w - 2)] * pattern[max(0, W - w - 2)]) % mod
            DP[h+1][w] %= mod
    print(DP[H][K - 1])

    return 0

if __name__ == "__main__":
    solve()