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 ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

H,W,K = II()
from itertools import product

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

#i番目のrowを通過後j+1にいる場合の数
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(1,H+1):
  for j in range(W):
    if 0<=j-1:
      a = list(product(['+','-'],repeat=W-1))
      counter = 0
      for a1 in a:
        if a1[j-1]!= '+':
          continue
        else:
          for k in range(1,W-1):
            if a1[k] == '+' and a1[k-1] == '+':
              break
            else:
              if k == W-2:
                counter += 1
      dp[i][j] += dp[i-1][j-1]*counter
      dp[i][j] %= mod
      
    if W-1>=j+1:
      a = list(product(['+','-'],repeat=W-1))
      counter = 0
      for a1 in a:
        if a1[j]!= '+':
          continue
        else:
          for k in range(1,W-1):
            if a1[k] == '+' and a1[k-1] == '+':
              break
            else:
              if k == W-2:
                counter += 1
      dp[i][j] += dp[i-1][j+1]*counter
      dp[i][j] %= mod

    a = list(product(['+','-'],repeat=W-1))
    counter = 0
    for a1 in a:
      if j <= W-2:
        if a1[j] == '+':
          continue
      if j-1>=0:
        if a1[j-1] == '+':
          continue
      for k in range(1,W-1):
        if a1[k] == '+' and a1[k-1] == '+':
          break
        else:
          if k==W-2:
            counter += 1
    dp[i][j] += dp[i-1][j]*counter
    dp[i][j] %= mod

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

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = int(1E9+7)

if W == 1:
    print(1)
else:
    dp = [[0 for _ in range(W)] for _ in range(H+1)]

    P = [1, 1, 2, 3, 5, 8, 13, 21]
    dp[0][0] = 1

    for h in range(1, H+1):
        for k in range(W):
            if k == 0:
                dp[h][k] = (P[k]*P[W-k-1]*dp[h-1][k] + P[k]*P[W-k-2]*dp[h-1][k+1]) % mod
            elif k == W-1:
                dp[h][k] = (P[k-1]*P[W-k-1]*dp[h-1][k-1] + P[k]*P[W-k-1]*dp[h-1][k]) % mod
            else:
                dp[h][k] = (P[k-1]*P[W-k-1]*dp[h-1][k-1] + P[k]*P[W-k-1]*dp[h-1][k] + P[k]*P[W-k-2]*dp[h-1][k+1]) % mod
    print(dp[H][K-1])

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    H, W, K = l_inpl()
    dp = create_grid(H+1, W)
    for i in range(W):
        dp[0][i] = 0
    dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            for k in range(0, 2**(W-1)): # 引ける横線の数
                ok = True
                for l in range(W-2):
                    if (k >> l) & 1 and (k >> (l+1)) & 1:
                        # 隣に線が引かれている
                        ok = False
                if not ok:
                    continue
                if j > 0 and (k >> (j-1)) & 1:
                    # jの左に横線が引かれるケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j < W-1 and (k >> j) & 1:
                    # jの右側に横線が引かれるケース
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    # jの両側に横線が引かれないケース
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache

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

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# 長さiの横幅に対して、隣り合わないように横線を引くパターン数
@lru_cache(maxsize=None)
def f(i):
    return (
        ModInt(1) if i <= 0 else
        ModInt(2) if i == 1 else
        f(i - 1) + f(i - 2)
    )


# 動的計画法により解を求める
@lru_cache(maxsize=None)
def g(i, j):
    return (
        ModInt(0) if i == 0 and j >= 2 or j == 0 or j == W + 1 else
        ModInt(1) if i == 0 and j == 1 else
        (
            g(i - 1, j - 1) * f(j - 3) * f(W - j - 1) +
            g(i - 1, j) * f(j - 2) * f(W - j - 1) +
            g(i - 1, j + 1) * f(j - 2) * f(W - j - 2)
        )
    )


ans = g(H, K)

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
  for j in range(2**(w-1)):
    tmp=format(j,'b')
    if len(tmp)!=w-1:
      tmp=(w-1-len(tmp))*'0'+tmp
    flag=True
    for l in range(1,w-1):
      if tmp[l]=='1' and tmp[l-1]=='1':
        flag=False
        break
    if flag==False:
      continue
    else:
      arr=[i for i in range(1,w+1)]
      for m in range(w-1):
        if tmp[m]=='1':
          arr[m],arr[m+1]=arr[m+1],arr[m]
      for m in range(w):
        dp[i][m]+=dp[i-1][arr[m]-1]%mod
print(dp[h][k-1]%mod)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

h,w,K = map(int,input().split())
if w == 1:
    print(1)
    quit()
dp = [[0]*(w) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        x,y,z = 0,0,0
        for k in range(2**(w-1)):
            b = [0]*(w-1)
            for l in range(w-1):
                if (k>>l) & 1:
                    if b[l-1] == 1:
                        break
                    b[l] = 1
            else:
                if j > 0 and j < w-1:
                    if b[j-1] == 1 and b[j] == 0:
                        x += 1
                    elif b[j-1] == 0 and b[j] == 0:
                        y += 1
                    elif b[j-1] == 0 and b[j] == 1:
                        z += 1
                elif j == 0:
                    if b[j] == 0:
                        y += 1
                    elif b[j] == 1:
                        z += 1
                elif j == w-1:
                    if b[j-1] == 0:
                        y += 1
                    elif b[j-1] == 1:
                        x += 1
        if j > 0:
            dp[i+1][j-1] += x*dp[i][j]
            dp[i+1][j-1] %= mod
        if j + 1 < w:
            dp[i+1][j+1] += z*dp[i][j]
            dp[i+1][j+1] %= mod
        dp[i+1][j] += y*dp[i][j]
        dp[i+1][j] %= mod
print(dp[-1][K-1])

Submission status: Accepted

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

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

# print(dp[0])
for i in range(1, h+1):
    if w == 1:
        dp[i][0] = dp[i-1][0]
        continue

    for bits in range(1<<(w-1)):
        if bits & (bits>>1) != 0:
            continue
        # print(bits, ''.join([str((bits>>j)&1) for j in range(w-1)]))

        for j in range(w-1):
            if (bits>>j) & 1 == 1:
                dp[i][j+1] += dp[i-1][j]
                dp[i][j+1] %= MOD
                dp[i][j] += dp[i-1][j+1]
                dp[i][j] %= MOD
            else:
                if j == 0 or (bits>>(j-1)) & 1 == 0:
                    dp[i][j] += dp[i-1][j]
                    dp[i][j] %= MOD

                if j == w-2:
                    dp[i][w-1] += dp[i-1][w-1]
                    dp[i][w-1] %= MOD
    # print(i, dp[i])

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

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10 ** 9 + 7

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

fib = {-2: 0, -1: 1, 0: 1}
for i in range(1, W):
    fib[i] = fib[i - 1] + fib[i - 2]

dp = defaultdict(int)

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

print(dp[(H, K)])

Submission status: Accepted

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

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

dp = [0]*W
dp[0] = 1
for h in range(H):
    dp_new=[0]*W
    for w in range(W):
        dp_new[w] = S[w]*S[W-1-w]*dp[w]
	
    for w in range(W-1):
        dp_new[w  ] += S[w]*S[W-2-w]*dp[w+1]
        dp_new[w+1] += S[w]*S[W-2-w]*dp[w  ]

    dp = [d%1000000007 for d in dp_new]

print(dp[K-1])

Submission status: Accepted

Solution code:
import numpy as np


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

if w == 1:
    print(1)
else:
    allstate = [""]
    befstate = [""]
    for i in range(w-1):
        for s in befstate:
            if s == "":
                allstate.append(s+str(i))
            else:
                last = int(s[-1])
                if (i-last)!=1:
                    allstate.append(s+str(i))
        befstate = allstate.copy()
        # print(befstate)
    # print(allstate)
    tot = len(allstate)
    for s in allstate:
        for c in s:
            temp = int(c)
            connect[temp][temp+1] += 1
            connect[temp+1][temp] += 1
    for i in range(w):
        temp = sum(connect[i])
        connect[i][i] = tot-temp
    buf = [0 for i in range(w)]
    buf[0] = 1
    for i in range(h):
        nbuf = [0 for i in range(w)]
        for j in range(w):
            for l in range(w):
                nbuf[l] += buf[j]*connect[j][l]
                nbuf[l]%=10**9+7
        buf = nbuf.copy()
    # print(buf)
    print(buf[k-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意MOD = 10**9+7

h,w,k = [int(i) for i in readline().split()]
MOD = 10**9+7

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



#dp[i][j] iまで見て位置j
dp = [[0]*(w) for i in range(h+1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        r=l=0
        if j < w-1: r = num[j]
        if j: l = num[j-1]

        if r:
            dp[i+1][j+1] += r*dp[i][j]
            dp[i+1][j+1] %= MOD
        dp[i+1][j  ] += (total-r-l)*dp[i][j]
        dp[i+1][j  ] %= MOD
        if l:
            dp[i+1][j-1] += l*dp[i][j]
            dp[i+1][j-1] %= MOD

#print(dp)
#print(total, num)
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
import itertools

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

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

bits = []
for r in range(w + 1):
    for bit in itertools.combinations(range(w - 1), r):
        if all(y - x > 1 for x, y in zip(bit, bit[1:])):
            bits.append(bit)

mod = 10 ** 9 + 7

for i in range(h):
    for j in range(w):
        for bit in bits:
            if j in bit:
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= mod
            elif (j - 1) in bit:
                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, raw_input().split())
dp = [[0]*w for i in range(h+1)]
dp[0][0] = 1
MOD = 10**9+7
def valid_mask():
    res = []
    for mask in range(1 << (w-1)):
        invalid = False
        for k in range(w-2):
            if (mask & 1 << k) > 0 and (mask & 1 << (k+1)) > 0:
                invalid = True
                break
        if not invalid:
            res.append(mask)
    return res

masks = valid_mask()

for i in range(h):
    for j in range(w):
        for mask in masks:
            if j < w-1 and (mask & 1 << j) > 0:
                dp[i+1][j+1] = (dp[i][j] + dp[i+1][j+1]) % MOD
            elif j - 1 >= 0 and (mask & (1 << (j-1))) > 0:
                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] % MOD

Submission status: Accepted

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

    patterns = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    x = [0] * (w - 1)
    for i in range(w-1):
        x[i] = patterns[i] * patterns[max(0, w-i-2)]

    y = [0] * w
    for i in range(w):
        y[i] = patterns[i] * patterns[max(0, w-i-1)]

    dp = [[0] * w for _ in range(h+1)]
    dp[0][0] = 1
    for j in range(h):
        for i in range(w):
            d = dp[j][i] * y[i]
            if i - 1 >= 0:
                d += dp[j][i-1] * x[i-1]
            if i + 1 < w:
                d += dp[j][i+1] * x[i]
            dp[j+1][i] = d % MOD
    print(dp[h][k-1])


main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
dp = [[]]
for i in range(0, W):
	dp[0].append(0)
dp[0][0] = 1
for i in range(0, H):
	next = []
	for j in range(0, W):
		next.append(0)
	for j in range(0, 2**(W-1)):
		lst = []
		m = j
		for k in range(0, W-1):
			lst.append(m%2)
			m //= 2
		flag = True
		for k in range(0, W-2):
			if lst[k] == 1 and lst[k+1] == 1:
				flag = False
				break
		if flag:
			notswapped = []
			for k in range(0, W):
				notswapped.append(True)
			for k in range(0, W-1):
				if lst[k] == 1:
					next[k+1] += dp[-1][k]
					next[k] += dp[-1][k+1]
					notswapped[k] = False
					notswapped[k+1] = False
			for k in range(0, W):
				if notswapped[k]:
					next[k] += dp[-1][k]
	dp.append(next)
print(dp[H][K-1]%(10**9+7))

Submission status: Accepted

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

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

p = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
def count(n):
    if n <= 0:
        return 1
    return p[n]

MOD = 1000000007

def main():
    H, W, K = rli()
    dp = [[0 for _ in range(W+2)] for _ in range(H+1)]
    dp[0][1] = 1
    for h in range(0, H):
        for w in range(1, W+1):
            dp[h+1][w] = dp[h][w-1]*count(w-3)*count(W-w-1)
            dp[h+1][w] += dp[h][w]*count(w-2)*count(W-w-1)
            dp[h+1][w] += dp[h][w+1]*count(w-2)*count(W-w-2)
            dp[h+1][w] %= MOD
    print(dp[H][K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
h, w, k = [ int(v) for v in input().split() ]

non_contiuous_list = [1,2]

end_0, end_1 = 1, 1
for i in range(8):
    end_1_new = end_0
    end_0_new = end_0 + end_1
    end_0, end_1 = end_0_new, end_1_new
    non_contiuous_list.append(end_0 + end_1)


def non_contiuous(x):
    global non_contiuous_list
    if x >= 0:
        return non_contiuous_list[x]
    else:
        return 1

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

for i in range(1,h+1):
    if w > 1:
        for j in range(w):
            a = max(0,w-2)
            b = max(0,w-3)
            if j == 0:
                reach[i][j] = reach[i-1][j] * non_contiuous(a) + reach[i-1][j+1] * non_contiuous(b)
            elif j == w - 1:
                reach[i][j] = reach[i-1][j] * non_contiuous(a) + reach[i-1][j-1] * non_contiuous(b)
            else:
                reach[i][j] = reach[i-1][j-1] * non_contiuous(j-2) * non_contiuous(w-j-2) + reach[i-1][j] * non_contiuous(j-1) * non_contiuous(w-j-2) + reach[i-1][j+1] * non_contiuous(j-1) * non_contiuous(w-j-3) 
    else:
        reach[i][0] = 1

    reach[i] = [ j % mod for j in reach[i] ] 

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

Submission status: Accepted

Solution code:
import sys

mod=10**9+7
fib=[1]*10
for i in range(2,10):
  fib[i]=fib[i-1]+fib[i-2]
#print(fib)

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

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

for i in range(1,H+1):
  dp[i][1]=(fib[W-1]*dp[i-1][1]+fib[W-2]*dp[i-1][2])%mod
  dp[i][W]=(fib[W-2]*dp[i-1][W-1]+fib[W-1]*dp[i-1][W])%mod
  for j in range(2,W):
    dp[i][j]=(fib[j-2]*fib[W-j]*dp[i-1][j-1]+fib[j-1]*fib[W-j]*dp[i-1][j]+fib[j-1]*fib[W-j-1]*dp[i-1][j+1])%mod
    
#print(dp)
print(dp[H][K])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 10 ** 9 + 7
dp_H1 = [[0] * 2 for _ in range(W + 1)]
#dp_H1: H=1の縦棒をi本用意した時、できるあみだの組み合わせはdp_H1[i][0]+dp_H1[i][1]

dp_row_where = [[0] * (W + 2) for _ in range(H + 1)]
#dp_row_where[i][j]: i行目の時点で、j本目の縦棒に到達できる組み合わせ

dp_H1[0][0] = 1
dp_H1[1][0] = 1

for i in range(2, W + 1):
	dp_H1[i][0] = dp_H1[i - 1][0] + dp_H1[i - 1][1]
	dp_H1[i][0] %= mod
	dp_H1[i][1] = dp_H1[i - 1][0]
	dp_H1[i][1] %= mod

dp_row_where[0][1] = 1

for i in range(1, H + 1):
	for j in range(1, W + 1):
		#j番目の縦棒から真下に降りる場合
		dp_row_where[i][j] += dp_row_where[i - 1][j] * sum(dp_H1[j - 1]) * sum(dp_H1[W - j])
		#print(sum(dp_H1[j - 1]), sum(dp_H1[W - j]))
		#j-1番目の縦棒から到達する場合
		dp_row_where[i][j] += dp_row_where[i - 1][j - 1] * sum(dp_H1[j - 2]) * sum(dp_H1[W - j])
		
		#j+1番目の縦棒から到達する場合
		dp_row_where[i][j] += dp_row_where[i - 1][j + 1] * sum(dp_H1[j - 1]) * sum(dp_H1[W - j - 1])
		
		dp_row_where[i][j] %= mod
		
print(dp_row_where[H][K])
#print(dp_H1)
#print(dp_row_where)

Submission status: Accepted

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

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

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

def pat(w) :
    if w < 1 :
        return 1
    else :
        return fib[w + 1]

for i in range(H) :
    for j in range(W) :
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * pat(j - 1) * pat(W - j - 2)) % MOD
        if j > 0 :
            dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j] * pat(j - 2) * pat(W - j - 2)) % MOD
        if j <= W - 2 :
            dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * pat(j - 1) * pat(W - j - 3)) % MOD

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

Submission status: Accepted

Solution code:
fib = [None] * 11
fib[0], fib[1] = 1, 2
for i in range(2, 11):
    fib[i] = fib[i-1] + fib[i-2]
mod = 1000000007
H, W, K = map(int, input().split())
if W == 1:
    print(1)
    quit()
dp = [[0] * W for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if 1 < j < W-2:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[j-2] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] * fib[W-j-3] % mod
        elif j == 1:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] * fib[W-j-3] % mod
        elif j == W-2:
            dp[i+1][j] += dp[i][j] * fib[j-1] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j-1] * fib[j-2] * fib[W-j-2] % mod
            dp[i+1][j] += dp[i][j+1] * fib[j-1] % mod
        elif j == 0:
            dp[i+1][0] = dp[i][0] * fib[W-2] + dp[i][1] * fib[W-3]
        elif j == W-1:
            dp[i+1][W-1] = dp[i][W-1] * fib[W-2] + dp[i][W-2] * fib[W-3]
        dp[i+1][j] %= mod
print(dp[H][K-1])

Submission status: Accepted

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

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


def calc(w):
    if w < 0:
        return 1
    return fib[w]


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

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

Submission status: Accepted

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

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


def calc(w):
    if w <= 0:
        return 1
    ret = 0
    for pattern in product([0, 1], repeat=w):
        pattern = ''.join(list(map(str, pattern)))
        if '11' not in pattern:
            ret += 1
    return ret


for h in range(H):
    for w in range(W):
        dp[h + 1][w] = (dp[h + 1][w] + dp[h][w] * calc(w - 1) * calc(W - w - 2)) % MOD
        if w + 1 < W:
            dp[h + 1][w + 1] = (dp[h + 1][w + 1] + dp[h][w] * calc(w - 1) * calc(W - w - 3) % MOD)
        if w - 1 >= 0:
            dp[h + 1][w - 1] = (dp[h + 1][w - 1] + dp[h][w] * calc(w - 2) * calc(W - w - 2) % MOD)

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

Submission status: Accepted

Solution code:
from functools import lru_cache

mod = 10 ** 9 + 7

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


@lru_cache(maxsize=w + 10)
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
    # 縦線n本のあみだくじのパターン数
    # 右端の縦線を引くかどうかで漸化式を作る


dp = [0] * w
dp[0] = 1
ndp = [0] * w

for _ in range(h):
    for i in range(w):
        ndp[i] += dp[i] * fib((i + 1) - 1) * fib(w - (i + 1))  # 真下
        ndp[i] %= mod
        if i - 1 >= 0:
            ndp[i - 1] += dp[i] * fib((i + 1) - 2) * fib(w - (i + 1))  # 左
            ndp[i - 1] %= mod
        if i + 1 < w:
            ndp[i + 1] += dp[i] * fib((i + 1) - 1) * fib(w - (i + 1) - 1)  # 右
            ndp[i + 1] %= mod
    dp = ndp
    ndp = [0] * w
print(dp[k])

Submission status: Accepted

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

dp = [0] * w
dp[0] = 1
ndp = [0] * w

for _ in range(h):
    for bits in range(1 << w - 1):
        if '11' in bin(bits): continue
        to = list(range(w))
        for i in range(w - 1):
            if (bits >> i) & 1:
                to[i], to[i + 1] = to[i + 1], to[i]
        for i in range(w):
            ndp[to[i]] += dp[i]
            ndp[to[i]] %= mod
    dp = ndp
    ndp = [0] * w
print(dp[k])

Submission status: Accepted

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

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

dp[0][0] = 1

for h in range(1,H+1):
    for w in range(0,W):
        a = 0
        b = 0
        c = 0
        
        Q = W-1
        for bit in range(1<<Q):
            invalid = False
            cur_seq = False
            for i in range(Q):
                on = (bit >> i) & 1
                if on & cur_seq:
                    invalid = True
                    break
                cur_seq = on

            # if there is sequential bar, then the combination is invalid
            if invalid:
                continue

            connected = False
            # if the combination has connection with w then count a or c
            # otherwise, inc b
            for i in range(Q):
                on = (bit >> i) & 1
                if on:
                    x = i
                    y = i+1
                    if x == w-1:
                        connected = True
                        a += 1
                    elif y == w+1:
                        connected = True
                        c += 1
            if not connected:
                b += 1

        cnt = 0
        if a > 0:
            cnt += a * dp[h-1][w-1]
        if b > 0:
            cnt += b * dp[h-1][w]
        if c > 0:
            cnt += c * dp[h-1][w+1]

        dp[h][w] = cnt

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

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

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

mod = int(1e9+7)

## 一列の中で可能な置換を全て保持しておく
perm_lst = []
def bfs():
    dq = deque() ## ((post permutation), next_line)
    dq.append(([],0))
    while dq:
        post, line = dq.popleft()
        if line < W: ## 何も繋がない
          post_tmp = deepcopy(post) ## もっといい書き方ありそう
          post_tmp.append((line,line))
          dq.append( (post_tmp,line+1) )
        if line < W-1: ## 隣とつなぐ
          post_tmp = deepcopy(post) ## もっといい書き方ありそう
          post_tmp.append((line,line+1))
          dq.append( (post_tmp,line+2) )
        if line == W:
          perm_lst.append(post)
bfs()
#print(perm_lst)

## dp[i][j]: i列目まで線を引いてjにいる場合の数の総数
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 perm in perm_lst:
    for j in range(len(perm)):
      if perm[j][0] != perm[j][1]:
        dp[i][perm[j][0]] += dp[i-1][perm[j][1]]
        dp[i][perm[j][1]] += dp[i-1][perm[j][0]]
      else:
        dp[i][perm[j][0]] += dp[i-1][perm[j][0]]
      
#print(dp)

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

Submission status: Accepted

Solution code:
import numpy as np
H, W, K = map(int, input().split())

if W == 1:
    print (1)
    exit()
MOD = 10 ** 9 + 7

#dp-tableの作成
lst = [[0] * (W) for i in range(H+2)]
dp = np.array(lst)
dp[0][0] = 1

def check(h): #h番目のX, Y, Zを検索
    count = 0
    for i in range(2**(W-1)):
        flag2 = True
        flag = False #一つ前が橋のとき、フラグをTrueにする
        for j in range(W-1):
            if flag2: #どこかで連続橋になったらそれ以降計算しない
                # print (j, end = ' ')
                if (i >> j) & 1: #1を橋とする
                    if flag: #連続で橋の時
                        count += 1
                        # print ('A', end = ' ')
                        flag = True
                        flag2 = False
                        break
                    else: #一つ前が橋では無い時-->ここに橋をかける
                        dp[H+1][j] += dp[h-1][j+1]%MOD
                        dp[H+1][j+1] += dp[h-1][j]%MOD
                        flag = True
                else:
                    if j == W-2: #最後の一本が橋でない時
                        dp[H+1][j+1] = dp[h-1][j+1]%MOD
                    if not flag: #連続で橋がかからない時、まっすぐ下ろす
                        dp[H+1][j] = dp[h-1][j]%MOD
                    else:
                        pass
                    flag = False
        if flag2: #最後まで条件を満たしていたら、H+1に記録していたものを通常の場所に移す
            dp[h][:] += dp[H+1][:]%MOD
            dp[h][:] = dp[h][:]%MOD
            # print (dp[H+1])
        dp[H+1][:] = 0
        # print ()
    # print (i)
    # print (count)
    return 0;

for i in range(H):
    check(i+1)

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

Submission status: Accepted

Solution code:
MOD = 1000000007

pattern = [0] * 10
pattern[0] = 1
pattern[1] = 1
for i in range(2, 8 + 1):
    pattern[i] = pattern[i-1] + pattern[i-2]


def single_down(idx_from, idx_to, W):
    if idx_from == idx_to:
        return pattern[idx_from - 1] * pattern[W - idx_from]
    else:
        left = min(idx_from, idx_to) - 1
        right = W - max(idx_from, idx_to)
        return pattern[left] * pattern[right]


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

    ptn = [[0] * W]
    ptn[0][0] = 1
    for h in range(1, H + 1):
        ptn.append([])
        ptn[h] = [0] * W
        for w in range(0, W):
            ptn[h][w] = ptn[h-1][w] * single_down(w+1, w+1, W) % MOD
            if w > 0:
                ptn[h][w] += ptn[h-1][w-1] * single_down(w, w+1, W) % MOD
            if w < W-1:
                ptn[h][w] += ptn[h-1][w+1] * single_down(w+2, w+1, W) % MOD
            ptn[h][w] %= MOD

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


if __name__ == '__main__':
    main()