Problem:


Score: 400 points

Problem Statement

Amidakuji is a traditional method of lottery in Japan.

To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.

A valid amidakuji is an amidakuji that satisfies the following conditions:

No two horizontal lines share an endpoint.

The two endpoints of each horizontal lines must be at the same height.

A horizontal line must connect adjacent vertical lines.

Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.

For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.

Constraints

H is an integer between 1 and 100 (inclusive).

W is an integer between 1 and 8 (inclusive).

K is an integer between 1 and W (inclusive).

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

1 3 2

Sample Output 1

1

Only the following one amidakuji satisfies the condition:

Sample Input 2

1 3 1

Sample Output 2

2

Only the following two amidakuji satisfy the condition:

Sample Input 3

2 3 3

Sample Output 3

1

Only the following one amidakuji satisfies the condition:

Sample Input 4

2 3 1

Sample Output 4

5

Only the following five amidakuji satisfy the condition:

Sample Input 5

7 1 1

Sample Output 5

1

As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.

Sample Input 6

15 8 5

Sample Output 6

437760187

Be sure to print the answer modulo 1\ 000\ 000\ 007.



Sample input:
1 3 2


Sample output:
1

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7
rec = []
for i in range(1 << (W - 1)):
    for j in range(W - 1):
        if i & 1 << j and i & 1 << (j + 1):
            break
    else:
        rec.append(i)

dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for k in range(W):
        for j in range(len(rec)):
            if k > 0 and (rec[j] & 1 << (k - 1)):
                dp[i][k - 1] += dp[i - 1][k]
                dp[i][k - 1] %= MOD
            elif k <= W - 2 and rec[j] & 1 << k:
                dp[i][k + 1] += dp[i - 1][k]
                dp[i][k + 1] %= MOD
            else:
                dp[i][k] += dp[i - 1][k]
                dp[i][k] %= MOD

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

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
L = [-1]*W
def line(n):##n本の縦線で引ける横線場合の数
  if(n<2):
    return 1
  else:
    if(L[n]!=-1):
      return L[n]
    else:
      a = 0
      for i in range(n-1):
        a += line(n-i-2)
      return a+1

arr = [[-1 for i in range(H)] for j in range(W)]
def ans(h,k):
  if(k<1 or k>W):
    return 0
  elif(h==0):
    if(k==1):
      return 1
    else:
      return 0
  else:
    if(arr[k-1][h-1]!=-1):
      return arr[k-1][h-1]
    else:
      arr[k-1][h-1]= ans(h-1,k)*(line(k-1)*line(W-k))+ans(h-1,k-1)*line(k-2)*line(W-k)+ans(h-1,k+1)*line(k-1)*line(W-k-1)
      arr[k-1][h-1] %= 1000000007
      return arr[k-1][h-1]
    
print(ans(H,K))

Submission status: Accepted

Solution code:
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper

@memorize
def amida(W):   # W本の棒に対する1行アミダの引き方
    if W<2:
        return 1
    else:
        return amida(W-1)+amida(W-2)

@memorize
def amida2(H, W, x):
    if H==0:
        return 1 if x==1 else 0
    a = 0 if x==1 else amida(x-2)*amida(W-x)*amida2(H-1, W, x-1)
    b = amida(x-1)*amida(W-x)*amida2(H-1, W, x)
    c = 0 if x==W else amida(x-1)*amida(W-x-1)*amida2(H-1, W, x+1)
    return (a+b+c)%1000000007
print(amida2(*map(int, input().split())))

Submission status: Accepted

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

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

dp[0][0] = 1

onerow_t = [0]*(w-1) # i番目の横棒があるような1行の線の引き方の場合の数
onerow_sum = 0

for i in range(1<<(w-1)):
    tf = [None]*(w-1)
    valid = True
    for d in range(w-1):
        if (i>>d)&1 != 0:
            tf[d] = True
        if d>0 and tf[d-1] and tf[d]:
            valid = False
            break
    # print(bin(i), tf, valid)
    if valid:
        onerow_sum += 1
        for d in range(w-1):
            if tf[d]:
                onerow_t[d] += 1

for i in range(1,h+1):
    for j in range(w):
        tmp = onerow_sum
        if 0<=j-1:
            dp[i][j] += onerow_t[j-1]*dp[i-1][j-1]
            tmp -= onerow_t[j-1]
        if j+1<w:
            dp[i][j] += onerow_t[j]*dp[i-1][j+1]
            tmp -= onerow_t[j]
        # print('i,j,tmp',i,j,tmp)
        dp[i][j] += tmp*dp[i-1][j]
        dp[i][j] = dp[i][j]%mod

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

Submission status: Accepted

Solution code:
# わかりやすい参考 https://atcoder.jp/contests/abc113/submissions/3544286#
H,W,K=map(int,input().split())
MOD=(10**9)+7

def fibonatti(N):
  fibonatti_seq=[1,1]
  for i in range(1,N):
    fibonatti_seq.append(fibonatti_seq[i-1]+fibonatti_seq[i])
  return fibonatti_seq

fibonatti_seq=fibonatti(8)

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

for i in range(H):
  for j in range(1,W+1):
    if j>=2:
      dp[i+1][j-1]+=dp[i][j]*fibonatti_seq[j-2]*fibonatti_seq[W-j]
      dp[i+1][j-1]%=MOD
    if j<=W-1:
      dp[i+1][j+1]+=dp[i][j]*fibonatti_seq[j-1]*fibonatti_seq[W-j-1]
      dp[i+1][j+1]%=MOD
    dp[i+1][j]+=dp[i][j]*fibonatti_seq[j-1]*fibonatti_seq[W-j]
    dp[i+1][j]%=MOD
print(dp[H][K])

Submission status: Accepted

Solution code:
h, w, k= map(int,input().split())
MOD = 10**9+7
dp, fib = [[0]*10 for i in range(h+1)], [1,1,2,3,5,8,13,21]
dp[0][1] = 1
if w == 1:
    print(1)
else:
    for i in range(1,h+1):
        for j in range(1, w+1):
            fromleft, fromabove, fromright = 0, 0, 0
            if j == 1: # 左端の場合
                fromabove = dp[i-1][j]*fib[w-1]
                fromright = dp[i-1][j+1]*fib[w-2]
            elif j == w: # 右端の場合
                fromleft = dp[i-1][j-1]*fib[w-2]
                fromabove = dp[i-1][j]*fib[w-1]
            else: # 中央当たりの場合
                fromleft = dp[i-1][j-1]*fib[j-2]*fib[w-j]
                fromabove = dp[i-1][j]*fib[j-1]*fib[w-j]
                fromright = dp[i-1][j+1]*fib[j-1]*fib[w-j-1]
            dp[i][j] = (fromleft+fromabove+fromright)%MOD
            #print(i, j, fromleft, fromabove, fromright)
    print(dp[h][k])
# print(dp)

Submission status: Accepted

Solution code:
# dp[h][x] 縦から h 列目を通過した (横棒を通った場合も含む) 直後に
#          左から x 本目の縦棒にいる場合の数

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

    if W == 1:
        print(1)
        return

    division = 1000000007
     
    amida = [[] for i in range(W+1)]
    amida[1] = ['0', '1']
    for x in range(2, W):
        for b in amida[x-1]:
            if b[-1] == '0':
                amida[x].append(b + '1')
            amida[x].append(b + '0')

    all_count = len(amida[W-1])
    bar = [0] * (W+1)
    for i in range(W-1):
        bar[i+1] = len(list(filter(lambda t:t[i] == '1', amida[W-1])))

    dp = [[0 for i in range(W+2)] for j in range(H+1)]
    dp[0][1] = 1
    for y in range(1,H+1):
        for x in range(1,W+1):
            dp[y][x] = dp[y-1][x-1] * bar[x-1] \
                     + dp[y-1][x+1] * bar[x] \
                     + dp[y-1][x] * (all_count - bar[x] - bar[x-1])

        #for x in range(1,W+1):
        #    print('%15d' % dp[y][x], end='')
        #print()
    print(dp[H][K] % division)

main()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
law = 1000000007
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] = (dp[row][col] + dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]) % law
            if col < w - 1:
                dp[row][col] = (dp[row][col] + dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]) % law
            dp[row][col] = (dp[row][col] + dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]) % law
print(dp[h][k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':


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

# dp[i][j] := i_th row で j に到達する場合の数
dp = [[0 for j in range(W+2)] for i in range(H+1)]
dp[0][1] = 1

# ge_patnum(p] := 横棒を引くところがp個並んでいるときの場合の数
patnum = [1, 2, 3, 5, 8, 13, 21]

def get_patnum(i):
	if i <= 0:
		return 1
	else:
		return patnum[i]

for i in range(H):
	for j in range(1, W+1):
		# 下へ移動
		move_down = dp[i][j] * get_patnum(j-2) * get_patnum(W-j-1)

		# 左下へ移動
		move_left = dp[i][j+1] * get_patnum(j-2) * get_patnum(W-j-2)

		# 右下へ移動
		move_right = dp[i][j-1] * get_patnum(j-3) * get_patnum(W-j-1)

		dp[i+1][j] = (move_down + move_left + move_right) % 1000000007
		
print(dp[H][K])

Submission status: Accepted

Solution code:
c = [1, 2, 3, 5, 8, 13, 21, 34, 55]

def count(n):
    if n < 0:
        return 1
    else:
        return c[n]
    
h, w, k = [int(i) for i in input().split(" ")]

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

def ul(i, j):
    if j == 0:
        return 0
    else:
        return count(j - 2) * count(w - j - 2) * p[i - 1][j - 1]

def uu(i, j):
    return count(j - 1) * count(w - j - 2) * p[i - 1][j]

def ur(i, j):
    if j == w - 1:
        return 0
    else:
        return count(j - 1) * count(w - j - 3) * p[i - 1][j + 1]

for i in range(1, h + 1):
    for j in range(0, w):
        p[i][j] = ul(i, j) + uu(i, j) + ur(i, j)
    
print(p[-1][k - 1] % 1000000007)

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)]
DP[0][0]=1
mod=1000000007
for i in range(h):
    for j in range(w):
        for p in range(1<<w-1):
            flag=True
            for q in range(w-2):
                if (p>>q)&1==1 and (p>>q+1)&1==1:
                    flag=False
            if flag:
                if j>=1 and (p>>j-1)&1==1:
                    DP[i+1][j-1]+=DP[i][j]
                    DP[i+1][j-1]%=mod
                elif j<=w-2 and (p>>j)&1==1:
                    DP[i+1][j+1]+=DP[i][j]
                    DP[i+1][j+1]%=mod
                else:
                    DP[i+1][j]+=DP[i][j]
                    DP[i+1][j]%=mod
print(DP[h][k-1])

Submission status: Accepted

Solution code:
def f(n):
    memo = {}
    def compute(n):
        if n in memo:
            return memo[n]
        if n == 2:
            return 2
        if n <= 1:
            return 1
        ret = compute(n-1) + compute(n-2)
        memo[n] = ret
        return ret
    return compute(n)


memo = {}

def gen_patterns(c, h, w, k):
    if (c, h) in memo:
        return memo[(c,h)]
    elif h == 1:
        if c == k:
            return f(c-1) * f(w-c) % 1000000007
        elif c+1 == k:
            return f(c-1)* f(w-c-1) % 1000000007
        elif c-1 == k:
            return f(c-2)*f(w-c) % 1000000007
        else:
            return 0
    else:
        ret = 0
        ret += f(c-1) * f(w-c) * gen_patterns(c,h-1,w,k)
        ret = ret % 1000000007
        if c != 1:
            ret += f(c-2)*f(w-c)*gen_patterns(c-1,h-1,w,k)
            ret = ret % 1000000007
        if c != w:
            ret += f(c-1)*f(w-c-1)*gen_patterns(c+1,h-1,w,k)
            ret = ret % 1000000007
        memo[(c,h)] = ret
        return ret


def main():
    H, W, K = list(map(int, input().split(' ')))
    print(gen_patterns(1, H, W, K))



if __name__ == '__main__':
    main()

Submission status: Accepted

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


def pattern(n):
    if n < 1:
        return 1
    elif n == 1:
        return 2
    elif n == 2:
        return 3
    else:
        return pattern(n-2) + pattern(n-1)


def memorize(func):
    cache = {}

    def inner(*args):
        if args in cache:
            return cache[args]
        else:
            ret = func(*args)
            cache[args] = ret
            return ret

    return inner


@memorize
def count(h, W, K):
    if h == 0:
        if K == 1:
            return 1
        else:
            return 0
    ret = 0
    if 1 < K:
        ret += count(h-1, W, K-1) * pattern(K-3) * pattern(W-K-1)
    ret += count(h-1, W, K) * pattern(K-2) * pattern(W-K-1)
    if K < W:
        ret += count(h-1, W, K+1) * pattern(K-2) * pattern(W-K-2)
    return ret


print(count(H, W, K) % 1000000007)

Submission status: Accepted

Solution code:
f = [0,1,1,2,3,5,8,13,21,34,55,89]
h,w,k = map(int,input().split())
a = [0]*(w+2)
b = [0]*(w+2)
a[1] =     1
for i in range(h):
  for j in range(1,w+1):
    b[j] =(f[j-1]*f[w-j+1]*a[j-1] + f[j]*f[w-j+1]*a[j] + f[j]*f[w-j]*a[j+1])%1000000007
  for j in range(1,w+1):
    a[j] = b[j]   

    
    
print(a[k])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def fib(n):
  if n == 0:
    return 1
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

def main():
  input = sys.stdin.readline
  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):
      if (j-1) >= 0:
        X = fib(j-1) * fib(W-(j+1))
        DP[i+1][j-1] += X * DP[i][j]

      if (j+1) <= (W-1):
        Z = fib(j) * fib(W-(j+2))
        DP[i+1][j+1] += Z * DP[i][j]

      Y = fib(j) * fib(W-(j+1))
      DP[i+1][j] += Y * DP[i][j]

  print(DP[H][K-1] % (10**9 + 7))


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

dp[0][1]=1

for i in range(h+1):
    for j in range(1,w+1):
        for l in range(2**(w-1)):
            p=bin(l)
            q=len(p)
            r=p.replace("11","")
            if q==len(r):
                r=p.replace("0b","")
                r="0"*(w-1-len(r))+r
                if j==1:
                    if r[0]=="0":
                        dp[i+1][j]+=dp[i][j]
                    else:
                        dp[i+1][j+1]+=dp[i][j]
                elif j==w:
                    if r[-1]=="0":
                        dp[i+1][j]+=dp[i][j]
                    else:
                        dp[i+1][j-1]+=dp[i][j]
                else:
                    if r[j-1]=="1":
                        dp[i+1][j+1]+=dp[i][j]
                    elif r[j-2]=="1":
                        dp[i+1][j-1]+=dp[i][j]
                    else:
                        dp[i+1][j]+=dp[i][j]
                   
print(dp[h][k]%1000000007)

Submission status: Accepted

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

# 以下の計算結果から、フィボナッチ数列であることがわかる
# existRight=[0 for _ in range(w-1)] # 右はしに横棒がある場合の数
# nonexistRight=[0 for _ in range(w-1)] # 右端に横棒がない場合の数
# nonexistRight[0]=1
# for i in range(1,w-1):
#     existRight[i]=nonexistRight[i-1]
#     nonexistRight[i]=existRight[i-1]+nonexistRight[i-1]

# patternSize[w-1]:縦軸w本のときのパターン数
# patternSize[-2],[-1]の対応のためのpatternSize[w],[w+1]
patternSize=[1for _ in range(w+2)]
patternSize[1]=2
for i in range(2,w):
    patternSize[i]=patternSize[i-1]+patternSize[i-2]

# 動的計画法
# a(h,x): h列目を通過した直後にx行目にいる場合の数とする
a=[[0for _ in range(w)]for _ in range(h+1)]
a[0][0]=1
for i in range(1,h+1):
    for j in range(0,w):
        # i-1行j列からの場合の数の漸化式
        if j!=0:
            a[i][j-1]+=a[i-1][j]*patternSize[j-2]*patternSize[w-1-j-1]
        a[i][j]+=a[i-1][j]*patternSize[j-1]*patternSize[w-1-j-1]
        if j!=w-1:
            a[i][j+1]+=a[i-1][j]*patternSize[j-1]*patternSize[w-1-j-2]

# import numpy as np
# print(np.array(a))
print(a[h][k-1]%1000000007)

Submission status: Accepted

Solution code:
fib = [1,1,2,3,5,8,13,21,34]
mod = 1000000007
H,W,K = list(map(int,input().split()))

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

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

print(dp[-1][K])

Submission status: Accepted

Solution code:
MOD = 1000000000 + 7


class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class BitDP2D(DP2D):
    def __init__(self, item_n: int, border: int, bit_n: int):
        super(BitDP2D, self).__init__(item_n, border)
        self.bit_n = bit_n

    def solve(self, expr: callable) -> list:
        for sbj_i in range(1, self.border+1):
            for bit in range(2 ** self.bit_n):

                for item_idx in range(1, self.item_n):
                    if (bit >> item_idx) & 1 and (bit >> (item_idx-1)) & 1:
                        break
                else:

                    for item_idx in range(1, self.item_n + 1):
                        if item_idx > 1 and (bit >> (item_idx-2)) & 1:  # from L
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx - 1]
                            self.table[sbj_i][item_idx] %= MOD
                        elif (bit >> (item_idx-1)) & 1:  # from R
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx + 1]
                            self.table[sbj_i][item_idx] %= MOD
                        else:  # from center
                            self.table[sbj_i][item_idx] += self.table[sbj_i - 1][item_idx]
                            self.table[sbj_i][item_idx] %= MOD
        return self.table


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    dp = BitDP2D(W, H, W-1)
    dp.table[0][1] = 1
    print(dp.solve(None)[H][K])

Submission status: Accepted

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

fib = {0:1, 1:1, 2:2} # n 本
for i in range(3,w):
    fib[i] = fib[i-1]+fib[i-2]

f = {} # x ~ x+1 に横線を引く方法が何通りか
for x in range(w-1):
    if(x in [0,w-2]):
        f[x] = fib[w-2]
    else:
        f[x] = fib[x]*fib[w-x-2]

g = {} # xに横線が引かれない方法が何通りあるか
for x in range(w):
    if(x in [0,w-1]):
        g[x] = fib[w-1]
    else:
        g[x] = fib[x]*fib[w-x-1]

# d[m][n] m行目を通った直後にn-1列目にいる
d = [[0 for _ in range(w)] for _ in range(h+1)]
d[0][0] = 1
for m in range(1,h+1):
    for n in range(w):
        d[m][n] = d[m-1][n]*g[n]
        if(n!=0):
            d[m][n] += d[m-1][n-1]*f[n-1]
        if(n!=w-1):
            d[m][n] += d[m-1][n+1]*f[n]
        d[m][n] %= 1000000007
print(d[h][k-1])

Submission status: Accepted

Solution code:
from functools import lru_cache

input_lst = list(map(int, input().split()))
h, w, k = input_lst[0], input_lst[1], input_lst[2]

def row_comb(w):
    if w < 0:
        return 0
    elif w <= 1:
        return 1
    elif w == 2:
        return 2
    else:
        return row_comb(w-2)+row_comb(w-1)

@lru_cache(maxsize=1000)
def trio(h,w):
    if h == 0:
        return [1] + [0 for i in range(10)]
    else:
        lst = []
        for i in range(1, w+1):
            if i == 1:
                lst.append(trio(h-1,w)[0] * row_comb(w-1) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-1) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i == 2:
                lst.append(trio(h-1,w)[0] * row_comb(w-2) + trio(h-1,w)[2] * row_comb(w-3) + trio(h-1,w)[1] * row_comb(w-2))
            elif i == w-1:
                lst.append(trio(h-1,w)[w-1] * row_comb(w-2) + trio(h-1,w)[w-3] * row_comb(w-3) + trio(h-1,w)[w-2] * row_comb(w-2))
            elif i > 2 and i < w-1:
                a = row_comb(i-2) * row_comb(w-i)
                b = row_comb(i-1) * row_comb(w-i-1)
                c = row_comb(i-1) * row_comb(w-i)
                lst.append(trio(h-1,w)[i-2] * a + trio(h-1,w)[i] * b + trio(h-1,w)[i-1] * c)
        lst = lst + [0 for i in range(10)]
        return lst
    
print(trio(h, w)[k-1] % 1000000007)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
def serch(yokobou=[[None]*(W-1)],depth=0):
    queue = []
    for arrange in yokobou:
        for b in [0,1]:
            if b == 0:
                copy = arrange[:]
                copy[depth] = 0
                queue.append(copy)
            elif b == 1:
                copy = arrange[:]
                if depth == 0:
                    copy[depth] = 1
                elif arrange[depth-1] != 1:
                    copy[depth] = 1
                else:
                    continue
                queue.append(copy)
    yokobou = queue[:]
    if depth == W-2:
        return yokobou
    return serch(yokobou,depth+1)

def possibility(j):
    X,Y,Z = 0,0,0
    for e in serch():
        if j == 0:
            if e[j] == 1:
                Z += 1
            elif e[j] == 0:
                Y += 1
            continue
        elif j == W-1:
            if e[j-1] == 1:
                X += 1
            elif e[j-1] == 0:
                Y += 1 
            continue
        if e[j-1] == 1:
            X += 1
        if e[j] == 1:
            Z += 1
        if e[j-1] == 0 and e[j] == 0:
            Y += 1
    return (X,Y,Z)

dp = [[0]*(W) for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        (X,Y,Z) = possibility(j)
        if j != 0:
            dp[i+1][j] += X*dp[i][j-1]
        if j != W-1:
            dp[i+1][j] += Z*dp[i][j+1]
        dp[i+1][j] += Y*dp[i][j]

ans = dp[H][K-1]
ans %= 10**9 + 7
print(ans)

Submission status: Accepted

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

def fibo(w):
    if w == 0:
        return 1
    if w == 1:
        return 1
    elif w == 2:
        return 2
    else:
        return fibo(w - 1) + fibo(w - 2)

dp = []
for i in range(w + 1):
    dp.append([])
for i in range(w + 1):
    for j in range(h + 1):
        dp[i].append(0)
for i in range(w + 1):
    if i == 1:
        dp[i][1] = fibo(w - 1)
    elif i == 2:
        dp[i][1] = fibo(w) - fibo(w - 1)
for j in range(2, h + 1):
    for i in range(1, w + 1):
        if i == 1:
            dp[i][j] = (dp[i][j - 1] * fibo(w - 1) + dp[i + 1][j - 1] * (fibo(w) - fibo(w - 1))) % mod
        elif i == w:
            dp[i][j] = (dp[i - 1][j - 1] * (fibo(w) - fibo(w - 1)) + dp[i][j - 1] * fibo(w - 1)) % mod
        else:
            dp[i][j] = (dp[i - 1][j - 1] * (fibo(i - 2) * fibo(w - i)) + dp[i][j - 1] * (fibo(i - 1) * fibo(w - i)) + dp[i + 1][j - 1] * (fibo(i - 1) * fibo(w - i - 1))) % mod
print(dp[k][h] % mod)

Submission status: Accepted

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

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

    if W == 1:
        print(1)
        return

    dp = []
    for h in range(H + 1):
        dp.append([0] * (W + 1))

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

    d = 10 ** 9 + 7
    dp[0][1] = 1
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            v = dp[h - 1][w] * ft[w - 1] * ft[W - w]
            if 2 <= w:
                v += dp[h - 1][w - 1] * ft[w - 2] * ft[W - w]
            if w <= W - 1:
                v += dp[h - 1][w + 1] * ft[w - 1] * ft[W - w - 1]
            dp[h][w] = v % d

    print(dp[H][K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = list(map(int,input().split()))
H = S[0]
W = S[1]
K = S[2]
fib = [1,2,3,5,8,13,21,0,1]
List = [1]
for x in range(0,W):
    List.append(0)

for x in range(0,H):
    X = tuple(List)
    for y in range(0,W):
        List[y] = fib[y-2]*fib[W-y-2]*X[y-1] + fib[y-1]*fib[W-y-2]*X[y] + fib[y-1]*fib[W-y-3]*X[y+1] 

ans = List[K-1] % 1000000007
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

MOD = 1000000007

def solve(H, W, K):
    if W == 1:
        return 1

    # dp = np.zeros((H+1, W), dtype=np.int64)
    dp = [[0 for _ in range(W)] for _ in range(H+1)]
    dp[0][0] = 1

    for h in range(1, H+1):
        # 横線を引ける可能性があるのは2^(W-1)通り
        # 実際は連続した横線は引けないのでもう少し少なくなる
        for i in range(1 << (W-1)):
            # 連続する横線がある場合はスキップ
            ok = True
            for j in range(1, W-1):
                if (i & (1 << j)) and (i & (1 << (j-1))):
                    ok = False
            if not ok:
                continue

            # print("i: ", end="")
            # for j in range(W-1):
            #     print(int(bool(i & (1 << j))), end="")
            # print()
            
            # DP
            # 各縦線についてループ
            for j in range(W):
                # 左側の縦線との間に横線あり
                if j != 0 and i & (1 << (j - 1)):
                    dp[h][j] += dp[h-1][j-1]
                    dp[h][j] %= MOD
                # 右側の縦線との間に横線あり
                elif j != W-1 and i & (1 << j):
                    dp[h][j] += dp[h-1][j+1]
                    dp[h][j] %= MOD
                # 横線なし
                else:
                    dp[h][j] += dp[h-1][j]
                    dp[h][j] %= MOD

    return dp[H][K-1]

print(solve(H, W, K))

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
p=[sum(('11'in str(bin(j)))^1for j in range(1<<i))for i in range(8)]
dp=[w*[0]for _ in[0]*-~h]
dp[0][0]=1
for i in range(1,h+1):
    for j in range(w):
        t=u=0
        if j:
            t=p[max(0,j-2)]*p[max(0,w-j-2)]
            dp[i][j]+=dp[i-1][j-1]*t
        if j<w-1:
            u=p[max(0,j-1)]*p[max(0,w-j-3)]
            dp[i][j]+=dp[i-1][j+1]*u
        dp[i][j]=(dp[i][j]+dp[i-1][j]*(p[w-1]-t-u))%(10**9+7)
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split());p=[sum(('11'in str(bin(j)))^1for j in range(1<<i))for i in range(8)];d=[w*[0]for _ in[0]*-~h];d[0][0]=1
for i in range(h):
 b=d[i]
 for j in range(w):
  t=u=D=0
  if j:t=p[max(0,j-2)]*p[max(0,w-j-2)];D=b[j-1]*t
  if j<w-1:u=p[max(0,j-1)]*p[max(0,w-j-3)];D+=b[j+1]*u
  d[i+1][j]=(b[j]*(p[w-1]-t-u)+D)%(10**9+7)
print(d[-1][k-1])

Submission status: Accepted

Solution code:
H,W,K = list(map(int,input().split()))
#i行(j+1)列にたどり着く場合の数
dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1
mod = 1000000007


for i in range(H):
    for j in range(W):
        for k in range(1<<W-1):
            ok = 1
            for l in range(W-2):
                if ((k >> l)&1 == 1)and((k>>l+1)&1 == 1):
                    ok = 0

            if ok:
                #左にたどる
                if (j >= 1) and ((k>>j-1)&1 == 1):
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= mod
                #右にたどる
                elif (j <= W-2) and ((k>>j)&1 == 1):
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= mod
                #直下
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= mod

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

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
l =[[0],[1]]
for i in range(2,W):
    for n,j in enumerate(l):
        if j[-1] < i-1:
            l.append(j+[i])
m =[0]*(W+1)
for i in l:
    for j in i:
        m[j]+=1
m[0]=0
wa =len(l)
ans=[{i:0 for i in range(W+2)} for _ in range(H+1)]
ans[0][1]=1
for i in range(H):
    for j in range(1,W+1):
        ans[i+1][j] = (wa-m[j-1]-m[j])*ans[i][j] +m[j-1]*ans[i][j-1]+m[j]*ans[i][j+1]
if W ==1:
    print(1)
else:
    print(ans[H][K]%(10**9+7))

Submission status: Accepted

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

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

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]
  

for j in range(w):
  a[0][j]=0
a[0][0]=1

for i in range(1,h+1):
  for j in range(w):
    if w==1:
      a[i][j]=a[i-1][j]
    elif j==0:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j+1]*fib(w-1)
    elif 1<=j<w-1:
      a[i][j]=a[i-1][j-1]*fib(w-j)*fib(j)+a[i-1][j]*fib(w-j)*fib(j+1)+a[i-1][j+1]*fib(w-j-1)*fib(j+1)
    elif j==w-1:
      a[i][j]=a[i-1][j]*fib(w)+a[i-1][j-1]*fib(w-1)
print(a[h][k-1]%1000000007)

Submission status: Accepted

Solution code:
def main():
    H, W, K = list(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(1 << (W - 1)):
            if '11' in bin(j):
                continue
            j <<= 1
            for w in range(W):
                if j & (1 << w):
                    dp[i + 1][w] += dp[i][w - 1]
                elif j & (1 << (w + 1)):
                    dp[i + 1][w] += dp[i][w + 1]
                else:
                    dp[i + 1][w] += dp[i][w]
                dp[i + 1][w] %= (10 ** 9 + 7)

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


if __name__ == '__main__':
    main()