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:
mod = 10**9+7
H,W,K = map(int,input().split())
a = [0]*20
a[0]=1
a[1]=1
for i in range(10):
    a[i+2]=a[i+1]+a[i]
dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for k in range(W):
        dp[h+1][k] += a[k]*a[W-k-1]*dp[h][k]
        dp[h+1][k] += a[k-1]*a[W-k-1]*dp[h][k-1]
        dp[h+1][k] += a[k]*a[W-k-2]*dp[h][k+1]
        dp[h+1][k] %= mod
print(dp[H][K-1])

Submission status: Accepted

Solution code:
mod=1000000007
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(1+H)]
dp[0][0]=1
C=[0]*(W+1)
C[0]=1
c=[[0,0] for i in range(1+W)]
c[0][0]=1
for i in range(1,1+W):
    c[i][0]=c[i-1][0]+c[i-1][1]
    c[i][1]=c[i-1][0]
for w in range(1,1+W):
    C[w]=c[w][0]
for i in range(H):
    for k in range(W):
        for l in range(k-1,k+2):
            if l<0 or l>=W:
                continue
            x=dp[i][k]*C[min(k,l)]*C[W-1-max(k,l)]%mod
            dp[i+1][l]=(dp[i+1][l]+x)%mod
print(dp[H][K-1])

Submission status: Accepted

Solution code:
import sys
MOD = 1000000007


def main():
    h, w, k = [int(x) for x in input().split()]
    fibonacci = [1, 2]
    for i in range(w - 2):
        fibonacci.append(fibonacci[i] + fibonacci[i + 1])
    pattern = [0 for _ in range(w)]
    pattern[0] = 1
    for _ in range(h):
        nextp = [0 for _ in range(w)]
        for i in range(w):
            nextp[i] = (pattern[i] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i > 0:
                nextp[i] += (pattern[i - 1] * (fibonacci[max(0, i - 2)] * fibonacci[max(0, w - (i + 2))])) % MOD
            if i < w - 1:
                nextp[i] += (pattern[i + 1] * (fibonacci[max(0, i - 1)] * fibonacci[max(0, w - (i + 3))])) % MOD
            nextp[i] %= MOD
        pattern = nextp
    print(pattern[k-1])


main()

Submission status: Accepted

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

dpW=[[1,0]for i in range(9)]
for i in range(1,9):
    dpW[i][0]=dpW[i-1][0]+dpW[i-1][1]
    dpW[i][1]=dpW[i-1][0]
#print(dpW)

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

for i in range(1,H+1):
    for j in range(1,W+1):
        
        dpH[i][j]+=dpH[i-1][j]*dpW[W-j][0]*dpW[j-1][0]
        if W-j-1>=0:
            dpH[i][j]+=dpH[i-1][j+1]*dpW[W-j-1][0]*dpW[j-1][0]
        if j-2>=0:
            dpH[i][j]+=dpH[i-1][j-1]*dpW[W-j][0]*dpW[j-2][0]
        dpH[i][j]%=(10**9+7)
print(dpH[H][K])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]
memo=[[None]*W for _ in range(H+1)]
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            return memo[cur+1][0]
        else:
            if memo[cur+1][0]==None:
                memo[cur+1][0]=dfs(cur+1,1)%mod
            if memo[cur+1][1]==None:
                memo[cur+1][1]=dfs(cur+1,2)%mod
            return (fib[W-1]*memo[cur+1][0]+fib[W-2]*memo[cur+1][1])%mod
    elif now==W:
        if memo[cur+1][W-2]==None:
            memo[cur+1][W-2]=dfs(cur+1,W-1)%mod
        if memo[cur+1][W-1]==None:
            memo[cur+1][W-1]=dfs(cur+1,W)%mod            
        return (fib[W-2]*memo[cur+1][W-2]+fib[W-1]*memo[cur+1][W-1])%mod
    else:
        if memo[cur+1][now-2]==None:
            memo[cur+1][now-2]=dfs(cur+1,now-1)%mod
        if memo[cur+1][now-1]==None:
            memo[cur+1][now-1]=dfs(cur+1,now)%mod     
        if memo[cur+1][now]==None:
            memo[cur+1][now]=dfs(cur+1,now+1)%mod  
        return (fib[W-now]*fib[now-2]*memo[cur+1][now-2]+fib[W-now]*fib[now-1]*memo[cur+1][now-1]+fib[W-now-1]*fib[now-1]*memo[cur+1][now])%mod
    
print(dfs(0,1))

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 10**9 + 7
draw_array = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

ans_array = [[0] * W for i in range(H)]

ans_array[0][0] = draw_array[W - 1]
ans_array[0][1] = draw_array[W - 2]

for i in range(1, H):
    for w in range(W):
        if w == 0:
            ans_array[i][w] = (ans_array[i - 1][w] * draw_array[W - 1]) + (
                ans_array[i - 1][w + 1] * draw_array[W - 2])
            ans_array[i][w] = ans_array[i][w] % mod
        elif w == W - 1:
            ans_array[i][w] = (ans_array[i - 1][w] * draw_array[W - 1]) + (
                ans_array[i - 1][w - 1] * draw_array[W - 2])
            ans_array[i][w] = ans_array[i][w] % mod
        else:
            from_left = ans_array[i - 1][w - 1] * (
                draw_array[w - 1] * draw_array[W - w - 1])
            from_left = from_left % mod
            from_center = ans_array[i - 1][w] * (
                draw_array[w] * draw_array[W - w - 1])
            from_center = from_center % mod
            from_right = ans_array[i - 1][w + 1] * (
                draw_array[w] * draw_array[W - w - 2])
            from_right = from_right % mod
            ans_array[i][w] = (from_left+from_center+from_right) % mod

# print(ans_array)
print(ans_array[H-1][K-1])

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
mod=10**9+7
fib=[1,1,2,3,5,8,13,21]

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(cur,now):
    if cur==H:
        if now==K:
            return 1
        else:
            return 0
    elif now==1:
        if W==1:
            return dfs(cur+1,1)%mod
        else:
            return (fib[W-1]*dfs(cur+1,1)+fib[W-2]*dfs(cur+1,2))%mod
    elif now==W:
        return (fib[W-2]*dfs(cur+1,W-1)+fib[W-1]*dfs(cur+1,W))%mod
    else:
        return (fib[W-now]*fib[now-2]*dfs(cur+1,now-1)+fib[W-now]*fib[now-1]*dfs(cur+1,now)+fib[W-now-1]*fib[now-1]*dfs(cur+1,now+1))%mod
    
print(dfs(0,1))

Submission status: Accepted

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

mod = 10 ** 9 + 7


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b


dp = [[0 for j in range(W + 5)] for i in range(H + 5)]  # dp[h][k]
dp[0][1] = 1
for i in range(1, H + 1):
    for j in range(1, W + 1):
        for t in [-1, 0, 1]:
            if 1 <= j + t <= W:
                used = [0 for _ in range(W + 1)]
                for y in [j, j - 1, j + t, j + t - 1]:
                    if y >= 0:
                        used[y] = 1
                l = -(used[0] == 0)
                for x in used:
                    if x == 0:
                        l += 1
                    else:
                        break
                r = -(used[W] == 0)
                for x in used[::-1]:
                    if x == 0:
                        r += 1
                    else:
                        break
                dp[i][j] += Fib(l + 3) * Fib(r + 3) * dp[i - 1][j + t]
                dp[i][j] %= mod
print(dp[H][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 r in range(H):
    for i in range(1 << (W - 1)):
        if '11' in bin(i): continue
        perm = [i for i in range(W)]
        for j in range(W - 1):
            if (i >> j) & 1:
                perm[j], perm[j + 1] = perm[j + 1], perm[j]
        for j in range(W):
            next_line = perm[j]
            ndp[next_line] += dp[j]
            ndp[next_line] %= mod
    dp = ndp.copy()
    ndp = [0] * W
print(dp[K])

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

import itertools
H, W, K = mi()

#hから、fr:左(-1), 真っ直ぐ(0), 右(1)から wに落ちてこれるような、h行の横棒の引き方は何種類あるかを返す
def howmany(fr, h, w):
  global W
  #領域外なので0を返す
  if w+fr==0 or w+fr==W+1: return 0
  #ここから先はちゃんと領域内から落ちてくる場合
  ans = 0
  #bit全探索。区間のbitにはstatus[0]~[W-2]でアクセス
  for status in itertools.product(('0','1'),repeat=W-1):
    #両端の区間を0で埋める（添字バグを回避するため
    status = ''.join(('0',''.join(status),'0')) #左から0011010みたいな感じで入ってる
    #wの左側の区間はw-1, 右側はwに対応している
    #1は横棒がある、0は横棒がない
    if '11' in status: continue
    elif fr==0:
      if status[w-1]=='1' or status[w]=='1': continue
    elif fr==1:
      if status[w]=='0': continue
    else: #fr==-1の場合
      if status[w-1]=='0': continue
    #これらをクリアした場合は条件を満たしていることになるのでans+=1
    ans += 1
  return ans % 1000000007

#DP[H行から]ストンと[W列に]落ちてくる場合の数
DP = [[0]*(W+2) for _ in range(H+1)]
DP[0][1] = 1

for h in range(1, H+1):
  for w in range(1, W+1):
  #DP[h][w]を求める。
  #まず、どこから落ちてくるか（最大3箇所）で3パターンに分ける。
    #1. まっすぐ落ちてくるパターン
    #まっすぐパターンは、「存在しない」が無いので、ifは要らない
    #DP[h-1][w]から落ちてくる
    DP[h][w] = ((DP[h-1][w-1] * howmany(-1, h, w))%1000000007 + (DP[h-1][w] * howmany(0, h, w))%1000000007 + (DP[h-1][w+1] * howmany(1, h, w))%1000000007)%1000000007

print(DP[H][K])

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

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

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def getBitsL(n, L):
    bits = [0] * L
    for i in range(L):
        bits[i] = (n & 1) == 1
        n >>= 1
    return bits

def main():
    H, W, K = i2nn()
    if W == 1:
        print(1)
        return
    # パターン数
    P = [[0] * W for _ in range(W)]
    for i in range(int(2**(W-1))):
        bits = getBitsL(i, W-1)
        ng = False
        for j in range(1, len(bits)):
            if bits[j-1] and bits[j]:
                ng = True
                break
        if ng:
            continue
        for j in range(W):
            if j == 0:
                if bits[j]:
                    P[j][j+1] += 1
                else:
                    P[j][j] += 1
            elif j == W-1:
                if bits[j-1]:
                    P[j][j-1] += 1
                else:
                    P[j][j] += 1
            else:
                if bits[j]:
                    P[j][j+1] += 1
                elif bits[j-1]:
                    P[j][j-1] += 1
                else:
                    P[j][j] += 1

    # 漸化式
    # A[縦][横] = パターン数
    A = [[0] * W for i in range(H+1)]
    A[0][0] = 1
    MOD = int(1e+9) + 7
    for h in range(H):
        for w1 in range(W):
            for w2 in range(W):
                A[h+1][w2] = (A[h+1][w2] + A[h][w1] * P[w1][w2]) % MOD
    print(A[H][K-1])
    #import numpy as np
    #print(np.array(P))
    #print(np.array(A))

main()

Submission status: Accepted

Solution code:
import itertools

h, w, k = [int(i) for i in input().split()]

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

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

for i in range(1, h + 1):
    for kuji_list in itertools.product([0, 1], repeat = w - 1):
        for l in range(len(kuji_list)-1):
            if kuji_list[l] == 1 and kuji_list[l+1] == 1:
                break
        else:
            for j in range(w):

                if j == 0:
                    if kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                elif j == w - 1:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                else:
                    if kuji_list[j-1] == 1:
                        dp[i][j] += dp[i - 1][j - 1]
                    elif  kuji_list[j] == 1:
                        dp[i][j] += dp[i - 1][j + 1]
                    else:
                        dp[i][j] += dp[i - 1][j]

                dp[i][j] %= (10 ** 9 + 7)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(H: int, W: int, K: int):
    dp = [[0] * (W + 2) for _ in range(H+1)]
    dp[0][1] = 1

    for h in range(H):
        for i in range(0, (1 << W), 2):
            f = True
            c = [0] * (W + 2)
            for w in range(1, W + 1):
                if ((i >> (w-1)) & 0x03) == 3:
                    f = False
                    break
                if i & (1 << (w - 1)):
                    c[w-1] += dp[h][w]
                elif i & (1 << w):
                    c[w+1] += dp[h][w]
                else:
                    c[w] += dp[h][w]
            if f:
                for j, cc in enumerate(c):
                    dp[h+1][j] += cc

    return dp[-1][K] % MOD


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
    result = solve(H, W, K)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict


def main():
    high, width, goal = map(int, input().split())

    move_dic = [defaultdict(int) for i in range(width + 2)]
    for i in range(2 ** (width - 1)):
        data = bin(i)[2:]
        if '11' in data:
            continue
        data = [0 for j in range(width - 1 - len(data))] + list(map(int, list(data)))
        # print(data)
        for j in range(width - 1):
            if data[j]:
                move_dic[j + 1][j + 2] += 1
                move_dic[j + 2][j + 1] += 1
            elif j < width - 2:
                if data[j + 1] == 0:
                    move_dic[j + 2][j + 2] += 1
                if j == 0:
                    move_dic[j + 1][j + 1] += 1
            else:
                move_dic[j + 2][j + 2] += 1
            # print(move_dic)

    dp = [[0 for i in range(width + 2)] for j in range(high + 2)]
    dp[1][1] = 1

    for i in range(2, high + 2):
        for j in range(1, width + 1):
            dp[i][j] = dp[i - 1][j - 1] * move_dic[j - 1][j] + dp[i - 1][j] * move_dic[j][j] + dp[i - 1][j + 1] * move_dic[j + 1][j]

    if width == 1:
        dp[high + 1][goal] = 1
    mod = 10 ** 9 + 7
    print(dp[high + 1][goal] % mod)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import chain
import numpy as np

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

def gen_row_pattern(i):
  # i番目以降だけ(inclusive)を使う
  if i>W:
    return [[]]
  # 下に流す
  result = [[(i,i)] + x for x in gen_row_pattern(i+1)]
  # 入れ替え
  if i <= W-1:
    result += [[(i,i+1)] + x for x in gen_row_pattern(i+2)]
  return result

patterns = gen_row_pattern(1)

import numpy as np
A = np.zeros((W+1,W+1),dtype=np.int64)
for x,y in chain(*patterns):
  A[x,y] += 1
  if x != y:
    A[y,x] += 1

# 最初は1番に居る
v = np.zeros(W+1,dtype=np.int64)
v[1] = 1

MOD = 10**9 + 7

for _ in range(H):
  v = np.mod(np.dot(A,v),MOD)

answer = v[K]
print(answer)

Submission status: Accepted

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

f = [1, 1]
while len(f)<=W:
  f.append(f[-2]+f[-1])

A = {(0,k):(1 if k==1 else 0) for k in range(1, W+1)}

for h in range(1, H+1):
  for x in range(1, W+1):
    pat = f[x-1]*f[W-x]*A[(h-1, x)]
    if x > 1:
      pat += f[x-2]*f[W-x]*A[(h-1, x-1)]
    if x < W:
      pat += f[x-1]*f[W-x-1]*A[(h-1, x+1)]
    A[(h, x)] = pat

print(A[(H, K)]%1000000007)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w,k = li()
k -= 1
MOD = 10**9 + 7

# 遷移行列
if w > 1:
    matrix = [[0]*w for _ in range(w)]
    for num in range(1 << (w-1)):
        if "11" in bin(num):
            continue

        ex = False
        for i, bit in enumerate(bin(num)[2:].zfill(w-1)):
            if bit == "1":
                ex = True
                matrix[i][i+1] += 1
                matrix[i+1][i] += 1

            elif ex:
                ex = False

            else:
                matrix[i][i] += 1

        if not ex:
            matrix[w-1][w-1] += 1

    # 適用
    dp = [1] + [0]*(w-1)
    for hi in range(h):
        nex = [0]*w
        for wj in range(w):
            for wk in range(w):
                nex[wj] += matrix[wj][wk] * dp[wk]
                nex[wj] %= MOD

        dp = nex

    print(dp[k])

else:
    print(1)

Submission status: Accepted

Solution code:
from functools import lru_cache
H, W, K = map(int, input().split())
mod = 1000000007
def amida(start, end):
    if end <= start:
        return 1
    if end > W-1:
        return 1
    return count(end-start+1)
@lru_cache(maxsize=None)
def count(n):
    res = 0
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    res += count(n-1)
    res += count(n-2)
    return res

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] * (amida(0, j-1) * amida(j+1, W-1)) % mod
        if j > 0:
            dp[i][j] += dp[i - 1][j-1] * (amida(0, j-2) * amida(j+1, W-1)) % mod
        if j < W-1:
            dp[i][j] += dp[i - 1][j+1] * (amida(0, j-1) * amida(j+2, W-1)) % mod
print(dp[H][K-1]%mod)

Submission status: Accepted

Solution code:
H,W,K = [ int(it) for it in input().split() ]
MOD = 1000000007

if (W==1):
    print (1)
else:
    import itertools as tool
    amd = [ it  for it in  tool.product( *([[0,1]]*(W-1)) ) if sum([ 1 if it[i]+it[i+1]==2 else 0 for i in range(W-2)] ) == 0   ]

    dp = [0]*W
    dp[0]=1


    for h in range(H):
        _dp = [0]*W
        for it in amd:
            w = 0
            for i in range(W):
                if w >= W-1 :
                    break
                if (it[w]==1):
                    _dp[w]+=dp[w+1]
                    _dp[w+1]+=dp[w]
                    w+=2
                else:
                    _dp[w]+=dp[w]
                    w+=1
            if (w==W-1):
                _dp[w]+=dp[w]
                w+=1
        dp = [ it%MOD for it in _dp]
    print (dp[K-1]%MOD)

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 cur in range(h):
    for bits in range(1 << (w - 1)):
        if '11' in bin(bits): continue
        # print(*map(lambda x: '-' if x == '1' else '.', bin(bits)[2:].zfill(w - 1)), sep='')
        for i in range(w):
            # print(bits >> i)
            if i < (w - 1) and (bits >> i) & 1:
                ndp[i + 1] += dp[i]
                ndp[i + 1] %= MOD
            elif i >= 1 and (bits >> (i - 1)) & 1:
                ndp[i - 1] += dp[i]
                ndp[i - 1] %= MOD
            else:
                ndp[i] += dp[i]
                ndp[i] %= MOD
    dp = ndp.copy()
    ndp = [0] * w
print(dp[k])

Submission status: Accepted

Solution code:
# あみだくじ
H, W, K = map(int,input().split())
# h番目のときに、k本目にたどりつく通り
dp = [[0 for j in range(W)] for i in range(H+1)] #高さHでK本
# dp[h][k] = dp[h-1][k-1]*(hにおけるk-1からkへの線の引き方) 
#          + dp[h-1][k]*(hにおける、k-1,k+1から線がひかれないとき) 
#          + dp[h-1][k*1]*(hにおけるk+1からkへの線の引き方)
# 線の引き方は、対象の線からフィボナッチ的に増えていく。
# なぜならx(引かない)の数だけ隣の候補が増える

def fib(n):
    fibonacci = [1,1,2,3,5,8,13,21,34]
    return fibonacci[n]

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

    dp[0][0] = 1
    for h in range(1,H+1):
        for k in range(W):
            if 0 < k < W-1: 
                num1 = dp[h-1][k-1]*fib(W-k-1)*fib(k-1)
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = dp[h-1][k+1]*fib(W-k-2)*fib(k)
            if k == 0: 
                num1 = 0
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = dp[h-1][k+1]*fib(W-k-2)*fib(k)
                
            if k == W-1: 
                num1 = dp[h-1][k-1]*fib(W-k-1)*fib(k-1)
                num2 = dp[h-1][k]  *fib(W-k-1)*fib(k)
                num3 = 0
            # print("({},{}):{}+{}+{}".format(h,k,num1,num2,num3))
            dp[h][k] = num1+num2+num3
    mod = 10**9+7
    print(dp[-1][K-1]%mod)

Submission status: Accepted

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

horz_pattern = 0
horz_pattern_fromleft = [0] * W
horz_pattern_fromright = [0] * W
for i in range(2**(W-1)):
  horz = bin(i+2**(W-1))[3:]
  ok = 1
  for j in range(W-2):
    if int(horz[j]) * int(horz[j+1]) == 1:
      ok = 0
      break
  if ok:
    horz_pattern += 1
    for bar in range(W-1):
      if horz[bar] == "1":
        horz_pattern_fromleft[bar+1] += 1
        horz_pattern_fromright[bar] += 1

dp = [[0 for w in range(W+2)] for h in range(H+1)]
dp[0][1] = 1
for h in range(1,H+1):
  for w in range(1,W+1):
    fromleft = horz_pattern_fromleft[w-1]
    fromright = horz_pattern_fromright[w-1]
    no_move = horz_pattern - fromleft - fromright
    dp[h][w] = (dp[h-1][w] * no_move
    		  + dp[h-1][w-1] * fromleft
      		  + dp[h-1][w+1] * fromright) % mod
print(dp[H][K])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

mod = 1000000007

c = defaultdict(lambda: 1)
c.update({0: 1, 1: 2, 2: 3, 3: 5, 4: 8, 5: 13, 6: 21})

dp = [{0: 0, 1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}, ]

for i in range(1, H+2):
    dp_i = {0: 0, W+1: 0}
    for j in range(1, W+1):
        dp_i[j] = dp[i-1][j-1]*c[j-3]*c[W-j-1] % mod + \
            dp[i-1][j]*c[j-2]*c[W-j-1] % mod + \
            dp[i-1][j+1]*c[j-2]*c[W-j-2] % mod
    dp.append(dp_i)

# H, Kを計算
print(dp[H][K] % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W,K = inpl()

num = [1,1,2,3,5,8,13,21]
# a_to_b[a][b] : a->b に行く高さ1の阿弥陀の数
a_to_b = [[0]*W for i in range(W)]
for a in range(W):
    for b in range(W):
        if a > b:
            a_to_b[a][b] = a_to_b[b][a]
        else:
            if abs(a-b) > 1:
                a_to_b[a][b] = 0
            else:
                a_to_b[a][b] = num[a]*num[W-b-1]

cnt = [0]*W
cnt[0] = 1
for h in range(H):
    next_cnt = [0]*W
    for a in range(W):
        for b in range(W):
            next_cnt[b] += a_to_b[a][b] * cnt[a]
    cnt = next_cnt[:]

print(cnt[K-1]%mod)

Submission status: Accepted

Solution code:
H,W,K=[int(a) for a in input().split(" ")]
wp = [0]*(W-1)
wv = [0]*W
curr, prev = [0]*W, [0]*W
prev[0] = 1
mod = 1000000007

def comb(n):
    prev, curr = [1,1], [0,0]
    if n<1: return 1
    for i in range(n-1):
        curr[0] = prev[1]
        curr[1] = prev[0]+prev[1]
        prev,curr = curr,prev
    return sum(prev)

for i in range(W):
    nl, nr = max(0,i-1), max(0, W-i-2)
    wv[i] = comb(nl)*comb(nr)

for i in range(W-1):
    nl, nr = max(0, i-1), max(0, W-i-3)
    wp[i] = comb(nl)*comb(nr)

for i in range(H):
    for i in range(W):
        curr[i]=0
    for i in range(W):
        curr[i] = (curr[i] + (wv[i]*prev[i])%mod)%mod
        if i>=1:
            curr[i-1] = (curr[i-1]+(wp[i-1]*prev[i])%mod)%mod
        if i<=W-2:
            curr[i+1] = (curr[i+1]+(wp[i]*prev[i])%mod)%mod
    prev, curr = curr, prev
print(prev[K-1]%mod)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
pattern=[]
n_pattern=[]
pattern.append(1)
n_pattern.append(0)
for i in range(w-1):
    pattern.append(0)
    n_pattern.append(0)
def f(x):
    if x==0:
        return 1
    elif x==1:
        return 1
    elif x==2:
        return 2
    elif x==3:
        return 3
    elif x==4:
        return 5
    elif x==5:
        return 8
    elif x==6:
        return 13
    elif x==7:
        return 21
for i in range(h):
    for j in range(w):
        a=f(w-1-j)*f(j)*pattern[j]
        if j>=1:
            b=f(w-1-j)*f(j-1)*pattern[j-1]
        else:
            b=0
        if j<=w-2:
            c=f(w-2-j)*f(j)*pattern[j+1]
        else:
            c=0
        n_pattern[j]=a+b+c
    for j in range(w):
        pattern[j]=n_pattern[j]
print(pattern[k-1]%(10**9+7))

Submission status: Accepted

Solution code:
from itertools import product

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, j, k in product(range(H), range(W), range(1 << (W - 1))):
    ok = True
    for l in range(W - 2):
        if (k >> l) & 1 and (k >> (l + 1)) & 1:
            ok = False
    if not ok:
        continue

    if j >= 1 and ((k >> (j - 1)) & 1):
        dp[i + 1][j - 1] += dp[i][j]
        dp[i + 1][j - 1] %= mod
    elif j <= W - 2 and (k >> j) & 1:
        dp[i + 1][j + 1] += dp[i][j]
        dp[i + 1][j + 1] %= mod
    else:
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
print(dp[H][K - 1])

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))

def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))

Submission status: Accepted

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return map(int, input_tuple)


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


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


def calc_bincount(w):
    bincount = {}
    for i in range(w - 1):
        bincount[i] = 2**i
        for j in range(2**i):
            while j:
                if j & 3 == 3:
                    bincount[i] -= 1
                    break
                j >>= 1
    bincount[-4] = bincount[-3] = bincount[-2] = bincount[-1] = 1
    return bincount


def main():
    h, w, k = intin()
    mod = 1000000007

    bincount = calc_bincount(w)

    counts_first = {}
    for i in range(1, w + 1):
        counts_first[i] = 0
    counts_first[1] = 1
    h_to_counts = {0: counts_first}

    for i in range(1, h + 1):
        prev_counts = h_to_counts[i - 1]
        h_to_counts[i] = {}
        for j in range(1, w + 1):
            h_to_counts[i][j] = 0

            # j - 1 --> j
            if j > 1:
                incr = ((bincount[j-3] * bincount[((w+1)-j)-2]) * prev_counts[j-1]) % mod
                h_to_counts[i][j] += incr
                h_to_counts[i][j] %= mod

            # j --> j
            incr = ((bincount[j-2] * bincount[((w+1)-j)-2]) * prev_counts[j]) % mod
            h_to_counts[i][j] += incr
            h_to_counts[i][j] %= mod

            # j + 1 --> j
            if j < w:
                incr = ((bincount[j-2] * bincount[((w+1)-j)-3]) * prev_counts[j+1]) % mod
                h_to_counts[i][j] += incr
                h_to_counts[i][j] %= mod

    print(h_to_counts[h][k])


if __name__ == '__main__':
    main()