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 numpy as np

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

valids = []
for i in range(2 ** (W - 1)):
    f0, f1 = False, False
    for bit in range(W - 1):
        if i >> bit & 1 == 0:
            f0 = True
            f1 = False
        else:
            if f1 == True:
                break
            f1 = True
            f0 = False
    else:
        valids.append(i)

M = np.zeros((W, W))

for valid in valids:
    m = np.eye(W)
    for bit in range(W - 1):
        if valid >> bit & 1 == 1:
            end = W - bit
            m[end-2:end, end-2:end] = np.array([[0, 1], [1, 0]])
    M += m

state = np.zeros((W,))
state[0] = 1
for i in range(H):
    state = M.dot(state)
    state %= int(1e9 + 7)

print(int(state[K - 1] % (int(1e9) + 7)))

Submission status: Accepted

Solution code:
mod=10**9+7
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

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

p=[1,1,1+1,1+2,1+3+1,1+4+3,1+5+6+1,1+6+10+4]

for i in range(w):
    a[0][i][i]=p[w-1-i]*p[i]
    if i<w-1:
        a[0][i][i+1]=a[0][i+1][i]=p[w-2-i]*p[i]

for r in range(1,h):
    for i in range(w):
        for j in range(w):
            a[r][i][j]=mul(a[r-1][i][j],p[w-1-j]*p[j])
            if j>0:
                a[r][i][j]+=mul(a[r-1][i][j-1],p[w-2-(j-1)]*p[j-1])
            if j<w-1:
                a[r][i][j]+=mul(a[r-1][i][j+1],p[w-2-j]*p[j])
                
print(a[h-1][0][k-1]%mod)

Submission status: Accepted

Solution code:
import collections
cd = collections.defaultdict
dp = cd(lambda: cd(int))
dp[0][1] = 1

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

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

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

print(dp[H][K])

Submission status: Accepted

Solution code:
import collections
cd = collections.defaultdict
memo = cd(lambda: cd(int))
memo[0][1] = 1

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

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


def count(h, w):
    if memo[h][w]:
        return memo[h][w]
    elif h == 0 or w == 0 or w == W + 1:
        return 0
    else:
        ret = count(h - 1, w) * fib[w - 1] * fib[W - w]
        ret += count(h - 1, w - 1) * fib[w - 2] * fib[W - w]
        ret += count(h - 1, w + 1) * fib[w - 1] * fib[W - w - 1]
        ret %= mod
        memo[h][w] = ret
        return ret


print(count(H, K))

Submission status: Accepted

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

draw_line = [0 for _ in range(W)]
draw_line[0] = 1
if W > 1:
    draw_line[1] = 1
for i in range(2, W):
    draw_line[i] = draw_line[i-1] + draw_line[i-2]

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1, H+1):
    for w in range(W):
        # from left
        if w > 0:
            dp[h][w] += dp[h-1][w-1] * draw_line[w-1] * draw_line[W-w-1]
        # from up
        dp[h][w] += dp[h-1][w] * draw_line[w] * draw_line[W-w-1]
        # from right
        if w < W-1:
            dp[h][w] += dp[h-1][w+1] * draw_line[w] * draw_line[W-w-2]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(H: int, W: int, K: int):
    # t[h][k]: h x W のあみだくじのうち, k+1本目にたどり着くパターンの総数
    t = [[0 for i in range(W)] for j in range(H+1)]
    t[0][0] = 1
    
    # d[w]: 縦w本のあみだくじに線をひくパターンの総数
    d = [0 for i in range(W+1)]
    d[0] = 1
    d[1] = 1
    for w in range(2, W+1):
        d[w] += d[w-1] #一番右に線を引かない場合
        d[w] += d[w-2] #一番右に線を引く場合

    for h in range(1, H+1):
        for k in range(W):
            if k > 0:
                # 左からくるパターン -*
                t[h][k] += t[h-1][k-1] * d[k-1] * d[W-k-1]
                t[h][k] %= MOD
            if k < W-1:
                # 右からくるパターン *-
                t[h][k] += t[h-1][k+1] * d[k] * d[W-k-2]
                t[h][k] %= MOD
            # 上からくるパターン ..
            t[h][k] += t[h-1][k] * d[k] * d[W-k-1]
            t[h][k] %= MOD

    print(t[H][K-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(H, W, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

h,w,k = m()

a = [1,1]

for i in range(98):
	a.append(a[-1] + a[-2])

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

for i in range(h):
	for j in range(w):
		l[i+1][j+1] = (l[i][j]*(a[max(0,j-1)] * a[w - 1 - j]) +l[i][j+1]*(a[j] * a[w - 1 - j]) + l[i][j+2]*(a[j] * a[max(0,w - 2 - j)]))%(10**9+7)
print(l[h][k])

Submission status: Accepted

Solution code:
from functools import lru_cache


def solve(string):
    h, w, k = map(int, string.split())
    c = [1, 1]
    for _ in range(1, 7):
        i, j = c[-2:]
        c.append(i + j)

    @lru_cache(h * w)
    def rec(pos, depth):
        if depth == h:
            return 1 if pos == 1 else 0
        ans = rec(pos, depth + 1) * c[pos - 1] * c[w - pos]
        if pos < w:
            ans += rec(pos + 1, depth + 1) * c[pos - 1] * c[w - pos - 1]
        if pos > 1:
            ans += rec(pos - 1, depth + 1) * c[pos - 2] * c[w - pos]
        return ans

    return str(rec(k, 0) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
import sys
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

h, w, k = nm()
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 j in range(w):
        for m in range(2 ** (w - 1)):
            count1 = 0
            count2 = 0
            count3 = 0
            mm = bin(m)[2:].zfill(w - 1)
            if '11' in mm:
                continue
            if j > 0:
                if mm[j - 1] == '1':
                    count1 += 1
                else:
                    if j < w - 1:
                        if mm[j] == '1':
                            count3 += 1
                        else:
                            count2 += 1
                    else:
                        count2 += 1
            else:
                if j < w - 1:
                    if mm[j] == '1':
                        count3 += 1
                    else:
                        count2 += 1
                else:
                    count2 += 1
            if j > 0:
                dp[i + 1][j - 1] += (dp[i][j] * count1) % mod
            if j < w - 1:
                dp[i + 1][j + 1] += (dp[i][j] * count3) % mod
            dp[i + 1][j] += (dp[i][j] * count2) % mod

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

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
if W==1:
    print(1)
    quit()

INF=1e9+7
dp=[[0]*W for i in range(H+1)]
dp[0][0]=1
d=W-1
a=max(0,d-1)
b=max(0,d-2)
f=max(0,d-3)
dic={0:0,1:1,2:2,3:4,4:7,5:12,6:20}
a=dic[a]+1
b=dic[b]+1
f=dic[f]+1
def func(w):
    c=dic[w-1]+1
    e=dic[d-w-1]+1
    return c*e
def func1(w):
    c=dic[w-1-1]+1
    e=dic[d-w-1]+1
    return c*e
def func2(w):
    c=dic[w-1]+1
    e=dic[d-w-1-1]+1
    return c*e
for i in range(H):
    for w in range(W):
        if w==0:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        elif w==W-1:
            dp[i+1][w]=(dp[i][w]*a)+(dp[i][w-1]*b)
            dp[i+1][w]%=INF
        elif w==1 :
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*b)+(dp[i][w+1]*f)
            dp[i+1][w]%=INF
        elif w==W-2:
            dp[i+1][w]=(dp[i][w]*b)+(dp[i][w-1]*f)+(dp[i][w+1]*b)
            dp[i+1][w]%=INF
        else:
            dp[i+1][w]=(dp[i][w]*func(w))+(dp[i][w-1]*func1(w))+(dp[i][w+1]*func2(w))
            dp[i+1][w]%=INF

print(int(dp[H][K-1]%INF))

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
dp=[[0]*(w+1) for i in range(h+2)]
dp[1][1]=1
p=10**9+7
line=[1]*(101)
line[2]=2
for i in range(3,101):
  line[i]=line[i-1]+line[i-2]
for i in range(1,h+1):
  for j in range(1,w+1):
    dp[i+1][j]+=dp[i][j]*line[j-1]*line[w-j]
    dp[i+1][j]%=p
    if 2<=j:
      dp[i+1][j]+=dp[i][j-1]*line[j-2]*line[w-j]
      dp[i+1][j]%=p
    if j+1<=w:
      dp[i+1][j]+=dp[i][j+1]*line[j-1]*line[w-j-1]
      dp[i+1][j]%=p
print(dp[h+1][k])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import itertools 
from collections import defaultdict

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


w = [[0] * 3 for _ in range(W)]
patterns = itertools.product([0, 1], repeat=W-1)

if W > 1:
    for i in range(W):
        for k, j in enumerate([-1, 0, 1]):
            if i - j < 0 or i - j > W - 1:
                continue
            
            num_use_pattern = 0
            for pattern in itertools.product([0, 1], repeat=W-1):
                if j == -1:
                    if i - 1 < 0: 
                        if pattern[i] == 0:
                            continue
                    else:
                        if not (pattern[i-1] == 0 and pattern[i] == 1):
                            continue
                elif j == 1:
                    if i >= W - 1:
                        if pattern[i-1] == 0:
                             continue
                    else:
                        if not (pattern[i-1] == 1 and pattern[i] == 0):
                            continue
                else:
                    if i - 1 < 0: 
                        if pattern[i] == 1:
                            continue
                    elif i >= W - 1:
                        if pattern[i-1] == 1:
                             continue
                    else:
                        if pattern[i] == 1 or pattern[i-1] == 1:
                            continue
                   
                if sum([pattern[l] * pattern[l-1] for l in range(1, W-1)]) > 0:
                    continue
                
                num_use_pattern += 1
                
            w[i][k] += num_use_pattern
     
    memo = defaultdict(lambda: defaultdict(lambda: -1))
    def recursive(h, k, num_p):
        if 0 > k or k >= W:
            return 0
        if memo[h][k] != -1:
            return memo[h][k] * num_p
        if h == H:
            if k == K - 1:
                return num_p
            else:
                return 0
             
        temp1 = 0
        temp2 = 0
        temp3 = 0
        temp1 = recursive(h + 1, k, w[k][1])
        if k > 0:
            temp2 = recursive(h + 1, k - 1, w[k][2])
        if k <= W - 1:
            temp3 = recursive(h + 1, k + 1, w[k][0])
            
        temp = temp1 + temp2 + temp3
        memo[h][k] = temp
        
        return temp * num_p
     
    print(recursive(0, 0, 1) % 1000000007)
else:
    print(1)

Submission status: Accepted

Solution code:
import itertools

import numpy as np

height, width, k = map(int, input().split())
k -= 1

MOD = 1000000007

# 1 つの行について valid な線の引き方を列挙
patterns = []
for r in range(width - 1):
    for pattern in itertools.combinations(range(width - 1), r):
        # 隣り合ってたらだめ
        if all(abs(a - b) != 1 for a, b in zip(pattern[:-1], pattern[1:])):
            patterns.append(pattern)

# counts[w][v]: 1 行で w から v へ行けるパターンの数
counts = np.zeros((width, width))
for pattern in patterns:
    for w in range(width):
        if w in pattern:
            counts[w][w + 1] += 1
        elif w - 1 in pattern:
            counts[w][w - 1] += 1
        else:
            counts[w][w] += 1
if width == 1:
    counts[0][0] = 1

# 0 から高さ h の w に行けるパターン数
# dp[h][w]
dp = np.zeros((height, width))
dp[0] = counts[0].copy()
for h in range(height - 1):
    dp[h + 1] = np.dot(dp[h], counts) % MOD

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

Submission status: Accepted

Solution code:
import itertools

height, width, k = map(int, input().split())
k -= 1

MOD = 1000000007

# 1 つの行について valid な線の引き方を列挙
patterns = []
for r in range(width - 1):
    for pattern in itertools.combinations(range(width - 1), r):
        # 隣り合ってたらだめ
        if all(abs(a - b) != 1 for a, b in zip(pattern[:-1], pattern[1:])):
            patterns.append(pattern)

# counts[w][v]: 1 行で w から v へ行けるパターンの数
counts = [[0 for _ in range(width)] for _ in range(width)]
for pattern in patterns:
    for w in range(width):
        if w in pattern:
            counts[w][w + 1] += 1
        elif w - 1 in pattern:
            counts[w][w - 1] += 1
        else:
            counts[w][w] += 1

# 0 から高さ h の w に行けるパターン数
# dp[h][w]
dp = [[0 for _ in range(width)] for _ in range(height)]
dp[0] = counts[0].copy()
for h in range(height - 1):
    for w in range(width):
        # w に来れるパターン数
        dp[h + 1][w] = sum([dp[h][v] * counts[v][w] for v in range(width)]) % MOD

if width == 1:
    print(1)
else:
    print(dp[-1][k])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline 
H, W, K = map(int, input().split())
dp = [[-1]*(W+1) for _ in range(H+1)]


def barcnt(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3
    elif n == 4:
        return 5
    elif n == 5:
        return 8
    elif n == 6:
        return 13
    elif n == 7:
        return 21
    else:
        return 0
    
def f(H, K):
    if K < 1 or K > W:
        return 0
    else:
        if dp[H][K] != -1:
            return dp[H][K]
        elif H == 1:
            if K == 1:
                dp[H][K] = barcnt(W-1)
                return dp[H][K]
            elif K == 2:
                dp[H][K] = barcnt(W-2)
                return dp[H][K]
            else:
                dp[H][K] = 0
                return 0
        else:
            dp[H][K] = f(H-1, K-1)*barcnt(max(0, K-2))*barcnt(max(0, W-K))
            dp[H][K] += f(H-1, K)*barcnt(max(0, K-1))*barcnt(max(0, W-K))
            dp[H][K] += f(H-1, K+1)*barcnt(max(0, K-1))*barcnt(max(0, W-K-1))
            dp[H][K] %= 10**9+7
            return dp[H][K]

print(f(H, K))

Submission status: Accepted

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

dp=[[0 for _ in range(W)] for _ in range(H+1)] #0~H,0~W-1
dp[0][0]=1
P=10**9+7


def check(l):
    for i in range(len(l)-1):
        if l[i+1]+l[i]==2:
            return False
    return True

for i in range(1,H+1):
    for w in range(W):
        X,Y,Z=0,0,0
        for j in range(2**(W-1)):
            tmp=[]
            for k in range(W-1):
                tmp.append(j>>k&1)
            if check(tmp):
                if w-1>=0 and (j>>(w-1))&1==1:
                    dp[i][w-1]+=dp[i-1][w]
                    dp[i][w-1]%=P
                elif w<=W-2 and j>>w&1==1:
                    dp[i][w+1]+=dp[i-1][w]
                    dp[i][w+1]%=P
                else:
                    dp[i][w]+=dp[i-1][w]
                    dp[i][w]%=P
print(dp[H][K-1])

Submission status: Accepted

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

dp=[[0 for _ in range(W)] for _ in range(H+1)] #0~H,0~W-1
dp[0][0]=1
P=10**9+7


def check(l):
    for i in range(len(l)-1):
        if l[i+1]+l[i]==2:
            return False
    return True

for i in range(1,H+1):
    for w in range(W):
        X,Y,Z=0,0,0
        for j in range(2**(W-1)):
            tmp=[]
            for k in range(W-1):
                tmp.append(j>>k&1)
            if check(tmp):
                if w-1>=0 and (j>>(w-1))&1==1:
                    X+=1
                elif w<=W-2 and j>>w&1==1:
                    Z+=1
                else:
                    Y+=1
            else:
                continue

        if w-1>=0: dp[i][w-1]=(dp[i][w-1]+dp[i-1][w]*X)%P
        dp[i][w]=(dp[i][w]+dp[i-1][w]*Y)%P
        if w+1<=W-1: dp[i][w+1]=(dp[i][w+1]+dp[i-1][w]*Z)%P

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 1000000007  # type: int


@functools.lru_cache(maxsize=None)
def f(x):
    if x <= 0:
        return 1
    elif x == 1:
        return 2
    else:
        return f(x-1) + f(x-2)


def solve(H: int, W: int, K: int):

    dp = [0]*(W+2)
    dp[1] = 1                   # スタート地点
    for h in range(H):
        buf = [0]*(W+2)
        for i in range(1, W+1):
            # 左からくる奴
            buf[i] += dp[i-1]*f(i-3)*f(W-i-1)
            buf[i] %= MOD
            # 真上から来る奴
            buf[i] += dp[i]*f(i-2)*f(W-i-1)
            buf[i] %= MOD
            # 右から来る奴
            buf[i] += dp[i+1]*f(i-2)*f(W-i-2)
            buf[i] %= MOD
        for i in range(1, W+1):
            dp[i] = buf[i]
    print(dp[K])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(H, W, K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1

for i in range(1, h+1):
    for j in range(0, 1 << (w-1)):
        skip = False
        for l in range(w-2):
            skip = skip or ((j >> l) & 1 and (j >> (l+1)) & 1)
        if not skip:
            for l in range(w):
                if l-1 >= 0 and (j >> (l-1)) & 1:
                    memo[i][l] += memo[i-1][l-1]
                elif l+1 < w and (j >> l) & 1:
                    memo[i][l] += memo[i-1][l+1]
                else:
                    memo[i][l] += memo[i-1][l]
                memo[i][l] = memo[i][l] % 1000000007

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

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
# (上から, 左右から)の通り数
memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1

# print(memo)

for i in range(1, h+1):
    for j in range(0, 1 << (w-1)):
        skip = False
        for l in range(w-2):
            skip = skip or ((j >> l) & 1 and (j >> (l+1)) & 1)
        # print(skip)
        if not skip:
            for l in range(w):
                if l-1 >= 0 and (j >> (l-1)) & 1:
                    memo[i][l] += memo[i-1][l-1]
                elif l+1 < w and (j >> l) & 1:
                    memo[i][l] += memo[i-1][l+1]
                else:
                    memo[i][l] += memo[i-1][l]
                memo[i][l] = memo[i][l] % 1000000007

# print(memo)
print(memo[h][k-1])

Submission status: Accepted

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

r = 10**9 + 7

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

dp[0][0]=1

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

if W!=1:
    for i in range(H):
        for j in range(W):
            if j==0:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j+1])%r
            elif j==W-1:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j-1])%r
            else:
                dp[i+1][j]=(num[j]*num[W-j-1]*dp[i][j]+num[j-1]*num[W-j-1]*dp[i][j-1]+num[j]*num[W-j-2]*dp[i][j+1])%r
    print(dp[H][K-1])
else:
    print(1)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
M = 1000000007
x = [ 0 for i in range(w)]
x[0] = 1
for i in range(1, w):
    for j in range((1<<i)):
        f = 0
        for l in range(i-1):
            if ((j>>l)&1) == 1 and ((j>>(l+1))&1) == 1:
                f = 1
                break
        if f == 0:
            x[i] += 1
    x[i] %= M
    #print(x[i])

def g(a):
    if a < 0: return 1
    return x[a]

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

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

Submission status: Accepted

Solution code:
from itertools import product
H,W,K = list(map(int, input().split()))
mod=int(1e9+7)

memo = [[0]*W for _ in range(H+1)]
memo[0][0]=1
#memo[h][w] = h行目のw列の場合の数

from itertools import product
def one_row(W):
    one_row_amida={i:{i:0 for i in range(W)} for i in range(W)}

    for p in product([0,1], repeat=W-1):
        if any([p[i]==1 and p[i+1]==1 for i in range(W-2)]):
            continue
        after = [i for i in range(W)]
        for i in range(W-1):
            if p[i]:
                after[i], after[i+1] = after[i+1], after[i]
        for i, a in enumerate(after):
            one_row_amida[i][a] += 1
    return one_row_amida

one_row_amida = one_row(W)

for h in range(H):
    for w in range(W):
        for j in range(W):
            memo[h+1][j] += memo[h][w] * one_row_amida[w][j]
    memo[h+1] = [x%mod for x in memo[h+1]]

answer = memo[H][K-1]

print(answer)

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

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

Submission status: Accepted

Solution code:
from itertools import product

mod = 1000000007
H, W, K = map(int, input().split())
dp = {}
dp[0] = [1] + [0]*(W-1)

for h in range(1, H+1):
    dp[h] = [0] * W
    for pattern in product([0, 1], repeat=W-1):
        c = 0
        for p in pattern:            
            c = ((c + 1) if p == 1 else 0)
            if c >= 2:
                break            
        if c >= 2:
            continue
        for i in range(0, W):
            if i <= W-2 and pattern[i] == 1:
                dp[h][i] = (dp[h][i] + dp[h-1][i+1]) % mod
            elif i >= 1 and pattern[i-1] == 1:
                dp[h][i] = (dp[h][i] + dp[h-1][i-1]) % mod
            else:
                dp[h][i] = (dp[h][i] + dp[h-1][i]) % mod
print(dp[H][K-1])

Submission status: Accepted

Solution code:
def way(h, w, k):
    if w == 1:
        return 1
    if [h, k] == [1, 1] or [h, k] == [1, 2]:
        return fibo[w - k]
    if h == 1:
        return 0
    if memo[h][k] != -1:
        return memo[h][k]
    re = way(h - 1, w, k) * fibo[k - 1] * fibo[w - k]
    if k != 1:
        re += way(h - 1, w, k - 1) * fibo[max(k - 2, 0)] * fibo[w - k]
    if k != w:
        re += way(h - 1, w, k + 1) * fibo[k - 1] * fibo[max(w - k - 1, 0)]
    memo[h][k] = re
    return re

h, w, k = map(int, input().split())
fibo = [1, 1]
for i in range(2, w):
    fibo += [fibo[i - 1] + fibo[i - 2]]
memo = [[-1] * (w + 1) for _ in range(h + 1)]

print(way(h, w, k) % 1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(H: int, W: int, K: int):
    comb_ = [[] for _ in range(W)]
    comb_[0] = [0, 1] # yes, no
    for i in range(1, W):
        comb_[i] = [comb_[i - 1][1], sum(comb_[i - 1])]
    comb = []
    for c in comb_:
        comb.append(c[0] + c[1])
    #print(comb)
    # dp[h + 1][w][2]
    dp = [[[0] * 2 for i in range(W)] for _ in range(H + 1)]
    dp[0][0][1] = 1
    for h in range(1, H + 1):
        for w in range(W):
            dp[h][w][0] = dp[h - 1][w][1]
        #print(dp)
        for w in range(W):
            dp[h][w][1] += dp[h][w][0] * comb[max(0, w - 1)] * comb[max(0, W - w - 2)]
            if w > 0:
                dp[h][w][1] += dp[h][w - 1][0] * comb[max(0, w - 2)] * comb[max(0, W - w - 2)]
            if w < W - 1:
                dp[h][w][1] += dp[h][w + 1][0] * comb[max(0, w - 1)] * comb[max(0, W - w - 3)]
    #print(dp)
    ret = dp[H][K - 1][1] % MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(H, W, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

H,W,K=map(int,input().split())
if W==1:
    print(1)
    sys.exit()
elif W==2:
    print(2**(H-1))
    sys.exit()

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

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

for i in range(1,H+1):
    a[i][0] = a[i-1][0]*dic[W-2] + a[i-1][1]*dic[W-3]
    for j in range(1,W-1):
        a[i][j]=a[i-1][j-1]*dic[j-2]*dic[W-j-2] + a[i-1][j]*dic[j-1]*dic[W-j-2] + a[i-1][j+1]*dic[j-1]*dic[W-j-3]
    a[i][W-1] = a[i-1][W-1]*dic[W-2] + a[i-1][W-2]*dic[W-3]


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
from functools import partial, reduce
from operator import mul
prod = partial(reduce, mul)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

fibo = [1, 1]
for i in range(2, 9):
    fibo.append(fibo[i - 1] + fibo[i - 2])

def main():
    H, W, K = LI()
    K -= 1
    dp = [0] * W
    dp[0] = 1
    for _ in range(H):
        pre = dp
        dp = [0] * W
        for w in range(W):
            # down
            cnt = fibo[max(0, w - 0)] * fibo[max(0, W - w - 1)]
            dp[w] += pre[w] * cnt
            dp[w] %= MOD
            # to L
            cnt = fibo[max(0, w - 1)] * fibo[max(0, W - w - 1)]
            if w - 1 >= 0:
                dp[w - 1] += pre[w] * cnt
                dp[w - 1] %= MOD
            # to R
            cnt = fibo[max(0, w - 0)] * fibo[max(0, W - w - 2)]
            if w + 1 < W:
                dp[w + 1] += pre[w] * cnt
                dp[w + 1] %= MOD
    ans = dp[K]
    return ans

print(main())

Submission status: Accepted

Solution code:
def valid(x):
    even_mask = 85  # 01010101
    odd_mask = 170  # 10101010
    return (x & odd_mask) >> 1 & (x & even_mask) == 0 and (x & odd_mask) << 1 & (x & even_mask) == 0

def yoko(x):
    a, b, c = 0, 0, 0
    for bit in range(1<<(W-1)):
        if not valid(bit):
            continue
        if bit >> (W - x - 1) & 1:
            a += 1
        elif W - x - 2 >= 0 and bit >> (W - x - 2) & 1:
            c += 1
        else:
            b += 1
    return a, b, c

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

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

for i in range(H):
    for j in range(W):
        a, b, c = yoko(j)
        if j - 1 >= 0:
            dp[i+1][j-1] += a * dp[i][j]
            dp[i+1][j-1] %= BIG
        dp[i+1][j] += b * dp[i][j]
        dp[i+1][j] %= BIG
        if j + 1 < W:
            dp[i+1][j+1] += c * dp[i][j]
            dp[i+1][j+1] %= BIG
print(dp[H][K-1])