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 = list(map(int,input().split()))
 
 
amida = [0 for i in range(8)]
amida[0]=1
amida[1]=2
amida[2]=3
amida[3]=5
amida[4]=8
amida[5]=13
amida[6]=21
amida[7]=34
 
def amida_num(k,l):
    return amida[max(k,0)]*amida[max(l,0)]
 
 
dp=[[0 for i in range(W)] for j in range(H+1)]
 
dp[0][0] = 1
 
if W!=1:
    for i in range(1,H+1):
        for j in range(W):
            if j==0:
                dp[i][j]=dp[i-1][j+1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            elif j==W-1:
                dp[i][j]=dp[i-1][j-1]*amida_num(0,W-3) + dp[i-1][j]* amida_num(0,W-2)
            else:
                dp[i][j]=dp[i-1][j-1]*amida_num(j-2,W-j-2) + dp[i-1][j]*amida_num(j-1,W-j-2) + dp[i-1][j+1]*amida_num(j-1,W-j-3)
    print(dp[H][K-1]%(10**9+7))
else:
    print(1)

Submission status: Accepted

Solution code:
def count(length, on):
    """Count of possible amida patterns"""
    if length < 0:
        return 1
    if length == 0:
        return 1
    ret = count(length - 1, False)
    if not on:
        ret += count(length - 1, True)
    return ret


# for i in range(1, 9):
#     print(count(i, True) + count(i, False))


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

    # Count
    B = [0 for _ in range(W)]
    B[0] = 1
    for j in range(H):
        C = [0 for _ in range(W)]
        for i in range(W):
            left_off = count(i - 1, False)
            left_on = count(i - 1, True)
            right_off = count(W - i - 2, False)
            right_on = count(W - i - 2, True)
            # print(i, left_off, left_on, right_off, right_on)

            if B[i] > 0:
                C[i] += B[i] * (left_off * right_off)

            if i > 0 and B[i - 1] > 0:
                C[i] += B[i - 1] * (left_on * right_off)

            if i < W - 1 and B[i + 1] > 0:
                C[i] += B[i + 1] * (left_off * right_on)

        B = [ci for ci in C]
        # print(B)

    # MOD = 1_000_000_007  # Underscore is not supported until 3.6
    MOD = 1000000007
    ANS = C[K - 1] % MOD
    print(ANS)

Submission status: Accepted

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

dp = [[1]]
for ww in range(w-1):
  dp[0].append(0)

for hh in range(1,h+1):
  dp.append([])
  for ww in range(w):
    dp[hh].append(0)
#    print("[hh={}, ww={}]".format(hh,ww))
    if ww != 0:
      dp[hh][ww] += dp[hh-1][ww-1] * ptn[ww-1] * ptn[w-1-ww]
#      print("added from left {} {} {} ".format(dp[hh-1][ww-1], ptn[ww-1], ptn[w-1-ww]))
    dp[hh][ww] += dp[hh-1][ww] * ptn[ww] * ptn[w-1-ww]
#    print("added from above {} {} {} ".format(dp[hh-1][ww] , ptn[ww] , ptn[w-1-ww]))
    if ww != w-1:
      dp[hh][ww] += dp[hh-1][ww+1] * ptn[ww] * ptn[w-ww-2]
#      print("added from right {} {} {} ".format(dp[hh-1][ww+1] , ptn[ww],  ptn[w-ww-2]))
    dp[hh][ww] = dp[hh][ww] % mod
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
# time complexity: O(HW2^W)
# space complexity: O(HW)

def violates(w_flags):
    prev_flag = w_flags & 1
    for shift in range(1, W - 1):
        flag = w_flags >> shift & 1
        if flag and prev_flag:
            return True
        prev_flag = flag
    return False


H, W, K = [int(elem) for elem in input().split()]
MOD = 10**9 + 7

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

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

for h in range(1, H + 1):
    for w_flags in range(2**(W - 1)):
        if violates(w_flags):
            continue
        for w in range(W):
            if w == 0:
                if w_flags & 1:
                    dp[h][0] += dp[h - 1][1]
                else:
                    dp[h][0] += dp[h - 1][0]
            elif w == W - 1:
                if w_flags >> W - 2 & 1:
                    dp[h][W - 1] += dp[h - 1][W - 2]
                else:
                    dp[h][W - 1] += dp[h - 1][W - 1]
            else:
                if w_flags >> w - 1 & 1:
                    dp[h][w] += dp[h - 1][w - 1]
                elif w_flags >> w & 1:
                    dp[h][w] += dp[h - 1][w + 1]
                else:
                    dp[h][w] += dp[h - 1][w]
            dp[h][w] %= MOD

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

Submission status: Accepted

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

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


if w == 1:
    num[0][0] = 1
elif w == 2:
    num[0][0] = 1
    num[0][1] = 1
    num[1][0] = 1
    num[1][1] = 1
else:
    for i in range(2 ** (w - 1)):
        for j in range(w - 2):
            if (((i >> j) & 1) == 1) and (((i >> (j + 1)) & 1) == 1):
                break
        else:
            for j in range(w):
                if j == 0:
                    if ((i >> j) & 1) == 1:
                        num[j][j + 1] += 1
                    else:
                        num[j][j] += 1
                elif j == w - 1:
                    if ((i >> (j - 1)) & 1) == 1:
                        num[j][j - 1] += 1
                    else:
                        num[j][j] += 1
                else:
                    if ((i >> j) & 1) == 1:
                        num[j][j + 1] += 1
                    elif ((i >> (j - 1)) & 1) == 1:
                        num[j][j - 1] += 1
                    else:
                        num[j][j] += 1

dp[0][0] = 1
mod = 10**9 + 7
for i in range(h):
    for j in range(w):
        for l in range(w):
            dp[i+1][j] += dp[i][l] * num[l][j]
            dp[i+1][j] %= mod

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

Submission status: Accepted

Solution code:
import numpy as np


MOD = 10**9 + 7
def powmod(mat, n, mod):
    result = np.eye(len(mat), dtype=np.int64)
    while n > 0:
        if n & 1:
            result = np.dot(result, mat) % mod
        mat = np.dot(mat, mat) % mod
        n >>= 1
    return result


H, W, K = [int(elem) for elem in input().split()]
trans_mat = np.zeros((W, W), dtype=np.int64)
initial_vec = np.zeros(W, dtype=np.int64)
initial_vec[0] = 1

for i in range(2**(W - 1)):
    flag = False
    for pos in range(W - 2):
        if (i >> pos & 1) and (i >> (pos + 1) & 1):
            flag = True
    if flag:
        continue
    for pos in range(W):
        if pos == 0:
            if i & 1:
                trans_mat[0, 1] += 1
            else:
                trans_mat[0, 0] += 1
        elif pos == W - 1:
            if (i >> W - 2) & 1:
                trans_mat[W - 1, W - 2] += 1
            else:
                trans_mat[W - 1, W - 1] += 1
        else:
            if (i >> (pos - 1)) & 1:
                trans_mat[pos, pos - 1] += 1
            elif (i >> pos) & 1:
                trans_mat[pos, pos + 1] += 1
            else:
                trans_mat[pos, pos] += 1

powed_mat = powmod(trans_mat, H, MOD)
print(np.dot(powed_mat, initial_vec)[K - 1] % MOD)

Submission status: Accepted

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

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

dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for b in range(2**(W-1)):
        if '11' in bin(b): continue
        b *= 2
        for j in range(W):
            if b&(1<<j):
                dp[i+1][j-1] += dp[i][j]
            elif b&(1<<(j+1)):
                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:
height, width, k = map(int, input().split())

start_w = 1
end_w = width

if end_w <= 1:
    print(1)
    exit()


def enum_no_relation_cases(n, m=0):
    front = n - (start_w + 1) - (m * (m - 1)) // 2
    rear = end_w - (n + 1) - (m * (m + 1)) // 2
    return int(enum_amida_all_cases(front) * enum_amida_all_cases(rear))


def enum_amida_all_cases(n):
    if n < 1:
        return 1
    return fibonacci(n+2)


f = [1, 1, 1] + ([0] * (end_w - 1))


def fibonacci(n):
    if f[n] == 0:
        f[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return f[n]


ans = [[0] * (1 + end_w + 1) for i in range(height + 1)]
ans[0][start_w] = 1
search_range = start_w + 1
for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        from_just_above = ans[h-1][w] * enum_no_relation_cases(w)
        from_upper_left = ans[h-1][w - 1] * enum_no_relation_cases(w, -1)
        from_upper_right = ans[h-1][w + 1] * enum_no_relation_cases(w, 1)
        ans[h][w] = from_just_above + from_upper_left + from_upper_right

    if search_range < end_w:
        search_range += 1

print(ans[height][k] % 1000000007)

Submission status: Accepted

Solution code:
height, width, k = map(int, input().split())

ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w, 1)
        ans[h][w] %= 1000000007
    if search_range < end_w:
        search_range += 1

print(ans[height][k])

Submission status: Accepted

Solution code:
def generate_bin_list(num, target_list_len):
    flags = []
    if target_list_len == 0:
        return flags
    for i in range(target_list_len):
        flags.append(0)
    b = list(bin(num))
    l_b = len(b)
    for j in range(0, l_b-2):
        flags[target_list_len-1-j] = int(b[l_b-1-j])
    return flags


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

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

A = {}
for i in range(H+1):
    A[i] = {}
    for j in range(W):
        A[i][j] = 0

n = pow(2, W-1)
patterns = []
for i in range(n):
    _p = generate_bin_list(i, W-1)
    current = _p[0]
    can_apply = True
    for i in range(1, len(_p)):
        if current == 1 and _p[i] == 1:
            can_apply = False
        current = _p[i]
    if can_apply:
        patterns.append(_p)

# start
A[0][0] = 1
mod = 1000000007

for h in range(1, H+1):
    for pattern in patterns:
        for x in range(W):
            if x == 0:
                if pattern[x] == 0:
                    A[h][x] += A[h-1][x]
                else:
                    A[h][x] += A[h-1][x+1]
            elif x == W-1:
                if pattern[x-1] == 0:
                    A[h][x] += A[h-1][x]
                else:
                    A[h][x] += A[h-1][x-1]
            else:
                if pattern[x-1] == 0 and pattern[x] == 0:
                    A[h][x] += A[h-1][x]
                if pattern[x-1] == 1:
                    A[h][x] += A[h-1][x-1]
                if pattern[x] == 1:
                    A[h][x] += A[h-1][x+1]
            A[h][x] %= mod

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

Submission status: Accepted

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

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

for i in range(H):
    for b in range(2**(W-1)):
        if '11' in bin(b): continue
        b *= 2
        for j in range(W):
            if b&(1<<j):
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= MOD
            elif b&(1<<(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])

Submission status: Accepted

Solution code:
def valid(x):
    prev = 0
    while x > 0:
        p = x & 1
        if p == 1 and prev == 1:
            return False
        prev = p
        x >>= 1
    return True

def mult(A, x):
    n = len(x)
    r = [0] * n
    for i in range(n):
        for j in range(n):
            r[i] = (r[i] + A[i][j] * x[j]) % MOD
    return r

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

A = [[0] * w for i in range(w)]
for i in range(2**(w-1)):
    if not valid(i): continue
    prev = 0
    for j in range(w):
        b = i & 1
        if b == 1:
            A[j][j+1] += 1
            A[j+1][j] += 1
        elif prev == 0:
            A[j][j] += 1
        prev = b
        i >>= 1

x = [1] + [0] * (w-1)
for i in range(h):
    x = mult(A, x)

print(x[k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 10**9 + 7
H, W, K = ds_in()

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

comb = [0] * 7
comb[0] = 1
comb[1] = 2
comb[2] = 3
for i in range(3, 7):
    comb[i] = comb[i-2] + comb[i-1]

for i in range(H):
    for i in range(1, W+1):
        dp[i][1] = dp[i][0] * (comb[max(0, i-2)] * comb[max(0, W-i-1)])\
                + dp[i-1][0] * (comb[max(0, i-3)] * comb[max(0, W-i-1)])\
                + dp[i+1][0] * (comb[max(0, i-2)] * comb[max(0, W-i-2)])
        dp[i][1] = dp[i][1] % MOD

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

print(dp[K][0])

Submission status: Accepted

Solution code:
import copy
import sys
H,W,K = list(map(int, input().split()))
if  W == 1:
  print(1)
  sys.exit()
D = [0 for i in range(W)]
T = copy.deepcopy(D)
D[0] = 1
F = [1, 1, 2, 3, 5, 8, 13, 21]
for i in range(H):
  T[0] = D[1] * F[W-2] + D[0] * F[W-1]
  T[W-1] = D[W-2] * F[W-2] + D[W-1] * F[W-1]
  for j in range(1, W-1):
    T[j] = D[j-1] * F[j-1] * F[W-j-1] \
             + D[j+1] * F[j] * F[W-j-2]\
             + D[j] * F[j] * F[W-j-1]
  D = copy.deepcopy(T)
print(D[K-1] % 1000000007)

Submission status: Accepted

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

# the number of horizonal line pattens at moving from line i to line j
hlineptn = [[0 for j in range(W)] for i in range(W)]

# calculate the number of horizonal line patterns
for hlinedig in range(1 << (W-1)):
    # convert digit to bit
    bitlist = [0 for i in range(W-1)]
    for i in range(len(bitlist)):
        if hlinedig & 1 << ((W-2)-i):
            bitlist[i] = 1

    # check illegal horizonal line
    illegalflg = False
    for i in range(len(bitlist)-1):
        if bitlist[i] and bitlist[i+1]:
            illegalflg = True
            break
    if illegalflg:
        continue

    # loop for before line
    for i in range(W):
        # move to left
        if i-1 >= 0 and bitlist[i-1]:
            hlineptn[i][i-1] += 1
        # move to right
        elif i+1 < W and bitlist[i]:
            hlineptn[i][i+1] += 1
        # move to current
        else:
            hlineptn[i][i] += 1

# calculate the number of move patterns from line 0
# and divide it by DIVISOR to get division remainder
mvptn = [[0 for w in range(W)] for h in range(H+1)]
mvptn[0][0] = 1
for h in range(1, H+1):
    for w in range(W):
        # from above left line
        if w-1 >= 0:
            mvptn[h][w] += mvptn[h-1][w-1] * hlineptn[w-1][w]
        # from above current line
        mvptn[h][w] += mvptn[h-1][w] * hlineptn[w][w]
        # from above right line
        if w+1 < W:
            mvptn[h][w] += mvptn[h-1][w+1] * hlineptn[w+1][w]

        # format to division remainder
        if mvptn[h][w] > DIVISOR:
            mvptn[h][w] %= DIVISOR

ans = mvptn[H][K-1]
print(ans)

Submission status: Accepted

Solution code:
h, w, k = [int(i) for i in input().split()]
h += 1
if w == 1:
    print(1)
    exit()
edge = [0 for i in range(w)]
edge[0] = 1
edge[1] = 2
for i in range(2, w):
    edge[i] = edge[i - 1] + edge[i - 2]
# print("edge:{}".format(edge))

dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(h - 1):
    for j in range(w):
        add = 1
        if 0 <= j - 1 < w:  # 小さい側
            add *= edge[j - 1]
            # print(add)
        if 0 <= w - j - 2 < w:  # 大きい側
            add *= edge[w - j - 2]
            # print(add)
        dp[i + 1][j] += dp[i][j] * add
        # print("h:{} j:{} j:{}".format(i, j, add))
        if j - 1 >= 0:
            add = 1
            if 0 <= j - 2 < w:
                add *= edge[j - 2]
            if 0 <= w - j - 2 < w:
                add *= edge[w - j - 2]
            dp[i + 1][j - 1] += dp[i][j] * add
            # print("h:{} j:{} j-1:{}".format(i, j, add))
        if j + 1 < w:
            add = 1
            if 0 <= j - 1 < w:
                add *= edge[j - 1]
            if 0 <= w - j - 3 < w:
                add *= edge[w - j - 3]
            dp[i + 1][j + 1] += dp[i][j] * add
            # print("h:{} j:{} j+1:{}".format(i, j, add))
        # for i in range(h):
        # print(dp[i])
print(dp[-1][k - 1] % 1000000007)

Submission status: Accepted

Solution code:
MOD = 1000000007


def main():
    H, W, K = map(int, input().split())
    dp = [[0 for _ in range(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 (ok):
                    if 1 <= j and (k >> (j - 1)) & 1:
                        dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j]) % MOD
                    elif j <= W - 2 and (k >> j) & 1:
                        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD
                    else:
                        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD

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

main()

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[1,1,2,3,5,8,13,21]
Amida=[[0]*W for h in range(H+1)]
for h in range(H+1):
  if W==1:
    break
  for w in range(W):
    if h==0:
      if w==0:
        Amida[h][w]=1
      else:
        Amida[h][w]=0
    elif w==0:
      Amida[h][w]=C[W-2]*Amida[h-1][w+1]+C[W-1]*Amida[h-1][w]
    elif w==W-1:
      Amida[h][w]=C[W-2]*Amida[h-1][w-1]+C[W-1]*Amida[h-1][w]
    else:
      Amida[h][w]+=(C[w-1]*C[W-w-1]*Amida[h-1][w-1])
      Amida[h][w]+=(C[w]*C[W-w-1]*Amida[h-1][w])
      Amida[h][w]+=C[w]*C[W-w-2]*Amida[h-1][w+1]
    Amida[h][w]=Amida[h][w]%1000000007
if W==1:
  if K==1:
    print(1)
  else:
    print(0)
else:
  print(Amida[H][K-1])

Submission status: Accepted

Solution code:
def main():
    """
    input:
        1 <= H <= 100
        1 <= W <= 8
        1 <= K <= W

    output:
        数列の項の最大公約数の最大値
    """
    H, W, K = map(int, input().split())

    # ans = visualize(H, W, K)
    ans = editorial(H, W, K)
    print(ans)


def f(H, W, K):
    """
    1-2の間に横棒を引く
    引き方: 0-H に引く組合せ
        x = sum(nCr(H, i) for i in range(H+1))

    2-3の間に横棒を引く
    引き方: 1-2の引いた部分以外に引くことができる
        startが1からなのでたどり方的に上に引く必要がないが
        それも正しい可能性のあるあみだくじなので考慮する

        x = 0
        for i in range(H+1):
            # i 本引いてあるなら、引いてない部分がMAX
            for j in range(H-i+1):
                x += sum(nCr(j, k) for k in range(j))

    たどり方
    1の一番高い棒から2へ向かう or なければそのまま下へ
    2から1or3の棒へ向かう or なければ下へ

    Kにたどり着くパターン or (全パターン - たどりつけないパターン)
        たぶん、縦と横を独立に考える。なんとなく
        下にH
        横にK-1, 右を+1左を-1としたとき
    """
    mod = 10 ** 9 + 7
    ans = 0

    return ans % mod


def visualize(H, W, K):
    valid_k = []
    for k in range(1 << (W - 1)):
        if not k & (k << 1):
            valid_k.append(k)

    for i in range(H):
        print("row", i+1)
        for j in range(W):
            for k in valid_k:
                h_bar = "{:08b}".format(k)[-(W-1):]
                h_bar = h_bar.replace("1", "_").replace("0", " ")

                header = " " + " ".join(str(i) for i in range(W)) + " "
                header = header.replace(" {} ".format(j), "[{}]".format(j))

                print(header)
                print(" |" + "|".join(list(h_bar)) + "| ")
                print(" " + " ".join("|" for _ in range(W)) + " ")
                print()

    return 1


def is_connected(k, W):
    # 2つの横線がつながっていないか
    ok = True
    for l in range(W - 2):
        if k >> l & 1 and k >> (l + 1) & 1:
            ok = False
            break

    ok2 = "11" not in bin(k)
    ok3 = not (k & (k << 1))
    assert ok == ok2 == ok3

    return ok


def editorial(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H+1)]
    dp[0][0] = 1
    # dp[H+1][W]
    # dp[i][j]: 上からicmまでの時点で、1からjに行ける数
    # dp[i + 1][a] += dp[i][j]: 下に1つ進んだとき、aに行ける数
    for i in range(H):
        for j in range(W):
            k_max = 1 << (W - 1)
            for k in range(k_max):
                # 2つの横線がつながっていないか
                ok = is_connected(k, W)
                if not ok:
                    continue

                #  pos:            L   S   R
                #  v_bar:   [j-1]_____[j]_____[j+1]
                #  h_bar:         j-1     j
                a = 0  # straight
                if j >= 1 and k >> (j - 1) & 1:  # left
                    a = - 1
                elif j < W - 1 and k >> j & 1:  # right
                    a = 1

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

    return dp[H][K - 1]


def a(H, W, K):
    """
    https://twitter.com/Py2K4/status/1059078331407028226
    """


def editorial_fib(H, W, K):
    """
    https://twitter.com/259_Momone/status/1059085685208956928
    導出: 棒が2本連続しない
    """


if __name__ == '__main__':
    main()

Submission status: Accepted

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

h = [ [ 0 for i in range(W) ] for j in range(H+1) ]
h[0][0] = 1
fib = [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

for hi in range(1, H+1):
    if W==1:
        h[H][K-1] = 1
    else:
        for wi in range(0, W):
            if wi==0:
                cen = fib[W+1]
                rig = fib[W]
                h[hi][wi] = cen * h[hi-1][wi] + rig * h[hi-1][wi+1]
            elif wi==W-1:
                lef = fib[W]
                cen = fib[W+1]
                h[hi][wi] = lef * h[hi-1][wi-1] + cen * h[hi-1][wi]
            else:
                lef = fib[wi+1] * fib[W-1-wi+2]
                cen = fib[wi+2] * fib[W-1-wi+2]
                rig = fib[wi+2] * fib[W-1-wi+1]
                h[hi][wi] = lef * h[hi-1][wi-1] + cen * h[hi-1][wi] + rig * h[hi-1][wi+1]

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

Submission status: Accepted

Solution code:
import itertools

def fibonacci(n):
    if (n == 0):
        f_n = 1
    elif (n == 1):
        f_n = 1
    else:
        f_n = fibonacci(n-1) + fibonacci(n-2)

    return f_n

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return fibonacci(len(left_x_amida) + 1) * fibonacci(len(right_x_amida) + 1)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return fibonacci(len(left_y_amida) + 1) * fibonacci(len(right_y_amida) + 1)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return fibonacci(len(left_z_amida) + 1) * fibonacci(len(right_z_amida) + 1)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)

dp_array = [0 for i in range(W)]
dp_array[0] = 1

for H_i in range(1, H + 1):
    new_dp_array = [0 for i in range(W)]
    for W_i in  range(W):
        if (W_i == 0):
            if(W == 1):
                new_dp_array[0] = dp_array[0] * amida_list[0][1]
            else:
                new_dp_array[0] = dp_array[0] * amida_list[0][1] + dp_array[1] * amida_list[0][2]
        elif (W_i == (W - 1)):
            new_dp_array[W - 1] = dp_array[W_i - 1] * amida_list[W_i][0] + dp_array[W_i] * amida_list[W_i][1]
        else:
            new_dp_array[W_i] = dp_array[W_i - 1] * amida_list[W_i][0] + dp_array[W_i] * amida_list[W_i][1] + dp_array[W_i + 1] * amida_list[W_i][2]
    dp_array = list(new_dp_array)

print(dp_array[K - 1] % 1000000007)

Submission status: Accepted

Solution code:
import itertools

def fibonacci(n):
    if (n == 0):
        f_n = 1
    elif (n == 1):
        f_n = 1
    else:
        f_n = fibonacci(n-1) + fibonacci(n-2)

    return f_n

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return fibonacci(len(left_x_amida) + 1) * fibonacci(len(right_x_amida) + 1)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return fibonacci(len(left_y_amida) + 1) * fibonacci(len(right_y_amida) + 1)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return fibonacci(len(left_z_amida) + 1) * fibonacci(len(right_z_amida) + 1)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1]
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1]
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]

print(dp_array[H][K - 1] % 1000000007)

Submission status: Accepted

Solution code:
import itertools

def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

def amida_all(amida_list, W):
    for i, j in itertools.product(range(W), range(3)):
        if(j == 0):
            amida_list[i][j] = X_amida_number(W, i)
        elif(j == 1):
            amida_list[i][j] = Y_amida_number(W, i)
        else:
            amida_list[i][j] = Z_amida_number(W, i)

    return amida_list

H, W, K = map(int, input().split())
amida_list = [[0]*3 for i in range(W)]
amida_list = amida_all(amida_list, W)

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1]
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1]
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * amida_list[W_i][0] + dp_array[H_i - 1][W_i] * amida_list[W_i][1] + dp_array[H_i - 1][W_i + 1] * amida_list[W_i][2]

print(dp_array[H][K - 1] % 1000000007)