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 sys

MOD = 10 ** 9 + 7

h, w, k = map(int, sys.stdin.readline().split())

def main():
    if w == 1:
        return 1
        
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)

    lcr = [(letter, 0) for letter in 'lcr']
    a = [dict(lcr) for _ in range(w)]
    for i in ok:
        j = 0
        while j < w:
            if i >> j & 1:
                a[j]['r'] += 1
                a[j+1]['l'] += 1
                j += 2
            else:
                a[j]['c'] += 1
                j += 1

    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for j in range(w):
            if j == 0:
                nex[j] = res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            elif j < w - 1:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c'] + res[j+1] * a[j]['r']
            else:
                nex[j] = res[j-1] * a[j]['l'] + res[j] * a[j]['c']
        for j in range(w):
            nex[j] %= MOD
        res = nex

    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

h, w, k = map(int, sys.stdin.readline().split())

def main():
    ok = []
    for i in range(2 ** (w - 1)):
        prev = False
        for j in range(w-1):
            if i >> j & 1:
                if prev:
                    break
                else:
                    prev = True
            else:
                prev = False
        else:
            ok.append(i)
        
    res = [0] * w
    res[0] = 1
    for _ in range(h):
        nex = [0] * w
        for i in ok:
            j = 0
            while j < w:
                if i >> j & 1:
                    nex[j] += res[j+1]
                    nex[j+1] += res[j] 
                    j += 2
                else:
                    nex[j] += res[j]
                    j += 1
        for j in range(w):
            nex[j] %= MOD
        res = nex
    
    return res[k-1]
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
mod = 10**9+7
dp = [[0 for i in range(W)] for j in range(H+1)]
dp[0][0] = 1
dp_x = [[0,0] for i in range(W)]
dp_o = [[0,0] for i in range(W)]
dp_x[0][0] = 1
dp_x[0][1] = 1
for i in range(W-1):
    dp_x[i+1][0] = dp_x[i][0]+dp_x[i][1]
    dp_x[i+1][1] =dp_x[i][0]
dp_o[0][0] = 1
dp_o[0][1] = 0
for i in range(W-1):
    dp_o[i+1][0] = dp_o[i][0] + dp_o[i][1]
    dp_o[i+1][1] =dp_o[i][0]
dp_o = [sum(e) for e in dp_o]
dp_x = [sum(e) for e in dp_x]
dp_o = [1]+dp_o
dp_x = [1]+dp_x
if W == 1:
    print(1)
    exit()
for h in range(0,H):
    for w in range(W):
        if w == 0:
            dp[h+1][0] += dp[h][0]*dp_x[W-1-1]%mod
            dp[h+1][0] += dp[h][1]*dp_o[W-1-1]%mod
        elif w == W-1:
            dp[h+1][w] += dp[h][w]*dp_x[W-1-1]%mod
            dp[h+1][w] += dp[h][w-1]*dp_o[W-1-1]%mod
        else:
            #no connection
            dp[h+1][w] += dp[h][w]*dp_x[w-1]*dp_x[W-w-2]%mod
            #right connection
            dp[h+1][w] += dp[h][w+1]*dp_x[w-1]*dp_o[W-w-2]%mod
            #left connection
            dp[h+1][w] += dp[h][w-1]*dp_o[w-1]*dp_x[W-w-2]%mod
print(dp[H][K-1]%mod)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    H,W,K = MI()
    K-=1

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

    max_bit = 1<<(W-1)
    for h in range(H):
        for mask in range(max_bit):
            before = 0
            ng = False
            for i in range(W):
                if before&(mask>>i):
                    ng = True
                    break
                before = mask>>i&1
            if ng:
                continue
            for i in range(W):
                if 1&mask>>i:
                    dp[h+1][i]+=dp[h][i+1]                
                    dp[h+1][i+1]+=dp[h][i]
                elif i==0 or not 1&mask>>(i-1):
                    dp[h+1][i]+=dp[h][i]
    print(dp[-1][K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
mod=1000000007
h,w,k=map(int,input().split())
n=2**(w-1)
if w==1:
    print(1)
    exit()

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

# print(tyuo)
# print(haji)
for l in range(h):
    for i in range(1<<w-1):
        a = str(bin(i))[2:].zfill(w-1)
        if a.count('11') >= 1:
            continue
        for j in range(w):
            if j==0:
                if i & (1<<w-2):
                    dp[l+1][j+1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            elif j==w-1:
                if i & 1:
                    dp[l+1][j-1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            else:
                if i & (1<<j-1):
                    dp[l+1][j-1]+=dp[l][j]
                elif i & (1<<j):
                    dp[l+1][j+1]+=dp[l][j]
                else:
                    dp[l+1][j]+=dp[l][j]
            # print(i,dp[l+1])
# print(dp)
print(dp[h][k-1]%mod)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MOD = 10**9 + 7
if W == 1:
    print(1)
    exit()
MR = [0] * W
ML = [0] * W
MS = [0] * W
for i in range(1 << (W-1)):
    S = bin(i)[2:]
    S = "0"*(W-1-len(S)) + S
    if S.find("11") >= 0:
        continue
    for j, s in enumerate(S):
        if s == "1":
            MR[j] += 1
            ML[j+1] += 1
    for j, (s1, s2) in enumerate(zip("0"+S, S+"0")):
        if s1 == s2 == "0":
            MS[j] += 1

DP = [[0] * W for _ in range(H+1)]
DP[0][0] = 1
for h in range(H):
    for w in range(W-1):
        DP[h+1][w+1] += DP[h][w] * MR[w] % MOD
        DP[h+1][w] += DP[h][w+1] * ML[w+1] % MOD
    for w in range(W):
        DP[h+1][w] += DP[h][w] * MS[w] % MOD

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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(H):
  for j in range(W):
    for b in range(pow(2, W - 1)):
      f = 0
      t = 0
      bb = []
      for k in range(W - 2, -1, -1):
        bb.append(int(b >= pow(2, k)))
        if b >= pow(2, k): b -= pow(2, k)
      for k in range(len(bb) - 1):
        if bb[k] and (bb[k + 1]):
          f = 1
          break
      if f: continue
      #print(bb, i)
      if j > 0:
        if bb[j - 1]:
          dp[i + 1][j - 1] += dp[i][j]
          dp[i + 1][j - 1] %= mod
          f = 1
      if j < W - 1:
        if bb[j]:
          dp[i + 1][j + 1] += dp[i][j]
          dp[i + 1][j + 1] %= mod
          f = 1
      if f == 0:
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod
print(dp[-1][K - 1])

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
K -= 1

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

valid_patterns = []
for pattern in itertools.product([True, False], repeat=W - 1):
    ok = True
    for a, b in zip(pattern, pattern[1:]):
        ok &= not (a and b)
    if ok:
        valid_patterns.append(pattern)
through = [0] * W
for pattern in valid_patterns:
    through[0] += pattern[0] is False
    through[-1] += pattern[-1] is False
    for i, (l, r) in enumerate(list(zip(pattern, pattern[1:]))):
        through[i + 1] += not l and not r

# dp[h][w]: 高さ h の左から w 番目の位置に来れるパターン数
dp = np.zeros((H + 1, W), dtype=int)
dp[0][0] = 1
for h in range(1, H + 1):
    dp[h] = dp[h - 1] * through % MOD
    for pattern in valid_patterns:
        for w, p in enumerate(pattern):
            if p:
                dp[h][w] += dp[h - 1][w + 1]
                dp[h][w + 1] += dp[h - 1][w]
        dp[h] %= MOD
print(dp[-1][K] % MOD)

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
b0,b1 = 1,0
c = [1]
for i in range(w-1):
  b0, b1 = b0+b1, b0
  c.append(b0+b1)
if w == 1:
  print(1)
  exit()
for i,v_i in enumerate(dp[:h]):
  for j,now in enumerate(v_i):
    if j == 0:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j+1] += (now * (c[max(0,w-3)])) % mod
    elif j == w-1:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j-1] += (now * (c[max(0,w-3)])) % mod
    else:
      dp[i+1][j-1] += (now * c[max(0,j-2)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j] += (now * c[max(0,j-1)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j+1] += (now * c[max(0,j-1)]*c[max(0,w-j-3)]) % mod
ans = dp[h][k-1] % mod
print(ans)

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
b0,b1 = 1,0
c = [1]
for i in range(w-1):
  b0, b1 = b0+b1, b0
  c.append(b0+b1)
d = [0] + c[1:]
if w == 1:
  print(1)
  exit()
for i,v_i in enumerate(dp[:h]):
  for j,now in enumerate(v_i):
    if j == 0:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j+1] += (now * (c[max(0,w-3)])) % mod
    elif j == w-1:
      dp[i+1][j] += (now * (c[max(0,w-2)])) % mod
      dp[i+1][j-1] += (now * (c[max(0,w-3)])) % mod
    else:
      dp[i+1][j-1] += (now * c[max(0,j-2)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j] += (now * c[max(0,j-1)]*c[max(0,w-j-2)]) % mod
      dp[i+1][j+1] += (now * c[max(0,j-1)]*c[max(0,w-j-3)]) % mod
ans = dp[h][k-1] % mod
print(ans)

Submission status: Accepted

Solution code:
def examA():
    X, Y = LI()
    ans = X + Y//2
    print(ans)
    return

def examB():
    N = I()
    T, A = LI()
    H = LI()
    cur = 10**9; ans = 0
    for i in range(N):
        now = abs(A - (T - H[i]*0.006))
        if cur>now:
            cur = now
            ans = i
    print(ans+1)
    return

def examC():
    N, M = LI()
    PY = [[]for _ in range(M)]
    d = defaultdict(int)
    ans = [[]for _ in range(M)]
    for i in range(M):
        PY[i] = LI()
        PY[i].append(i)
    PY.sort(key=lambda x:x[1])
    for p,y,s in PY:
        d[p] +=1
        cur = str(p).zfill(6) + str(d[p]).zfill(6)
        ans[s] = cur
    for v in ans:
        print(v)
    return

def examD():
    global mod
    H, W, K = LI()
    fibo = [1]*(W+1)
    for i in range(W-1):
        fibo[i+2] = fibo[i+1] + fibo[i]
    dp = [[0]*(W) for _ in range(H+1)]
    dp[0][0] = 1
#    print(fibo)
    for i in range(H):
        for j in range(W):
            dp[i+1][j] += dp[i][j]*fibo[j]*fibo[W-j-1]%mod
            dp[i+1][j] %=mod
            if j-1>=0:
                dp[i+1][j-1] += dp[i][j]*fibo[j-1]*fibo[W-j-1]%mod
                dp[i+1][j-1] %=mod
            if j+1<W:
                dp[i+1][j+1] += dp[i][j]*fibo[j]*fibo[W-j-2]%mod
                dp[i+1][j+1] %=mod
    ans = dp[H][K-1]
    print(ans)
#    print(dp)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
if W==1:
    print(1)
    exit()
dp=[[0]*W for _ in range(H+1)]

dp[0][0]=1
import itertools
A=list(itertools.product([1,0],repeat=W-1))
#print(A)
B=[]

for a in A:
    flg=True
    for i in range(len(a)-1):
        if a[i+1]==1 and a[i]==1:
            flg=False
    if flg:
        B.append(a)
#print(B)
for h in range(1,H+1):
    for b in B:
        for w in range(W):
            if w==0:
                dp[h][w]+=dp[h-1][w]*(1-b[w])+dp[h-1][w+1]*b[w]
            elif w==W-1:
                dp[h][w]+=dp[h-1][w]*(1-b[w-1])+dp[h-1][w-1]*b[w-1]
            else:
                dp[h][w]+=dp[h-1][w]*(1-b[w-1])*(1-b[w])+dp[h-1][w-1]*b[w-1]+dp[h-1][w+1]*b[w]
#print(dp)
#print(dp[H-1][K-1])
print(dp[H][K-1]%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




h, w, k = LI()
fib_list = [1] * w
for i in range(2, w):
    fib_list[i] = fib_list[i - 1] + fib_list[i - 2]


dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        # そのまま行くパターン
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * fib_list[j] * fib_list[w - j - 1] % mod) % mod
        if j < w - 1:
            # 配るdp
            # 右側に配る
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * fib_list[j] * fib_list[w - j - 2] % mod) % mod
        if j > 0:
            # 左側に配る
            dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * fib_list[j - 1] * fib_list[w - j - 1] % mod) % mod




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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = MAP()

# あみだくじとして妥当かの判定
def check(S):
    for i in range(W-1):
        # 1つでも隣り合う場所に横棒があればNG
        if S & 1<<i and S & 1<<(i+1):
            return False
    return True

# dp[i][S][j] := i段目まで見て、今の段の横棒の状態がSで、j本目の縦棒に行く通り数
dp = list3d(H+1, 1<<W, W+1, 0)
dp[0][0][1] = 1
for i in range(H):
    for S1 in range(1<<W):
        # 左端はただの番兵なので、立っていたらスキップ
        if S1 & 1:
            continue
        # あみだくじとして妥当でない集合は全てスキップ
        if not check(S1):
            continue
        for S2 in range(1<<W):
            if S2 & 1:
                continue
            if not check(S2):
                continue
            for j in range(1, W+1):
                # 左に棒があれば左に遷移
                if S2 & 1<<(j-1):
                    dp[i+1][S2][j-1] += dp[i][S1][j]
                    dp[i+1][S2][j-1] %= MOD
                # 右に棒があれば右に遷移
                elif S2 & 1<<j:
                    dp[i+1][S2][j+1] += dp[i][S1][j]
                    dp[i+1][S2][j+1] %= MOD
                # 棒がなければ真下に遷移
                else:
                    dp[i+1][S2][j] += dp[i][S1][j]
                    dp[i+1][S2][j] %= MOD
ans = 0
for S in range(1<<W):
    ans += dp[H][S][K]
    ans %= MOD
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
L = [1, 2, 3, 5, 8, 13, 21]
for i in range(H):
    for j in range(W):
        if j > 0:
            dp[i+1][j] += dp[i][j-1]*L[max(0, j-2)]*L[max(0, W-2-j)]
        if j < W-1:
            dp[i+1][j] += dp[i][j+1]*L[max(0, j-1)]*L[max(0, W-3-j)]
        dp[i+1][j] += dp[i][j]*L[max(0, j-1)]*L[max(0, W-2-j)]
        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+2)
dp[1] = 1

#左右の余白を埋めるパターン数
ref = [1,2,3,5,8,13,21]
pat = lambda l,r:ref[max(l,0)] * ref[max(r,0)]

for i in range(h):
	_dp = [0]*(w + 2)
	for j in range(1,w+1):
		_dp[j] = dp[j-1]*pat(j-3,w-j-1) + dp[j]*pat(j-2,w-j-1) + dp[j+1]*pat(j-2,w-j-2)
		_dp[j] %= mod
	dp = _dp
print(dp[k])

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
mod = 10**9+7
dp = [[0]*(w+2) for _ in range(h+1)]
dp[0][1] = 1

#左右の余白を埋める場合の数
ref = [1,2,3,5,8,13,21]
pat = lambda l,r:ref[max(l,0)]*ref[max(r,0)]

for i in range(h):
	for j in range(1,w+1):
		dp[i+1][j] = dp[i][j-1]*pat(j-3,w-j-1) + dp[i][j]*pat(j-2,w-j-1) + dp[i][j+1]*pat(j-2,w-j-2)
		dp[i+1][j] %= mod
print(dp[-1][k])

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    dp = [[0] * W for _ in range(H + 5)]
    dp[0][0] = 1
    MOD = 10 ** 9 + 7
    for h in range(H):
        for i in range(1 << W-1):
            a = str(bin(i))[2:].zfill(W-1)
            if a.count('11') >= 1:
                continue
            for w in range(W):
                if w == 0:
                    if a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    elif a[w] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                elif w == W - 1:
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    elif a[w-1] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                else:
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= MOD
                    elif a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                    else:
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD

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







if __name__ == "__main__":
    main()

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
for i in range(1,W):
    dp[0][i] = 0

for h in range(H):
    for w in range(W):
        
        for j in range((1<<W-1)):
            ok = True
            for k in range(1,W-1):
                if (j>>k)%2 == 1 and (j>>k-1)%2 == 1:
                    ok = False 
                    break
            if ok :
                #right
                if w < W-1 and (j>>w)%2 == 1:
                    dp[h+1][w+1] += dp[h][w]
                    dp[h+1][w+1] = dp[h+1][w+1]%mod
                #left
                elif w > 0 and (j>>w-1)%2 == 1:
                    dp[h+1][w-1] += dp[h][w]
                    dp[h+1][w-1] = dp[h+1][w-1]%mod
                else:
                    dp[h+1][w] += dp[h][w]
                    dp[h+1][w] = dp[h+1][w]%mod

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

Submission status: Accepted

Solution code:



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

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

#dp[i][j]：左からj番目の縦棒で上からiの地点を訪れる場合の数
dp = [[0 for _ in range(W)] for _ in range(H+1)]
#最初は一番左上
dp[0][0] = 1

MOD = 10**9+7
for i in range(H):
    # 横棒のパターンを全探索。横棒は二つの縦棒の間にできるので、W-1箇所入れられるのでそれぞれについてあるORない
    # 1ならそこに横棒がある
    for yoko in range(2**(W-1)):
        if "11" in bin(yoko):
            continue
        
        yoko = bin(yoko)[2:].zfill(W-1)

        for j in range(W):
            #dp[i][j]からどこに行くか考える
            #print(j, len(yoko))
            # 左に行く横棒がある場合
            if j != 0 and  yoko[j-1] == "1":
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] = dp[i+1][j-1] % MOD

            # 右に行く横棒がある場合
            
            elif j != W-1 and yoko[j] == "1":
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] = dp[i+1][j+1] % MOD

            # そのまま降りる（横棒がない）場合
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][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+1) for _ in range(h+1)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        for k in range(2**(w-1)):
            ok=True
            for l in range(w-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    ok=False
            if ok:
                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:
import sys
from math import factorial
MOD = 10**9+7
h, w, k = [int(i) for i in sys.stdin.readline().split()]
# memo_ls[n] : n本の平行線に対し、あみだくじの条件を満たす組み合わせの数
memo_ls2 = [[0 for x in range(2)] for y in range(8)]
memo_ls2[1][0] = 1
for i in range(2,8):
    memo_ls2[i][0] = memo_ls2[i-1][1] + memo_ls2[i-1][0]
    memo_ls2[i][1] = memo_ls2[i-1][0]
memo_ls = [sum(i) for i in memo_ls2]
# memo_ls3[j][i] : j番目にiにいる通り数
memo_ls3 = [[0 for i in range(w)] for j in range(h+1)]
memo_ls3[0][0] = 1
for j in range(1,h+1):
    for i in range(w):
        if i > 0:
            memo_ls3[j][i] += memo_ls3[j-1][i-1] * memo_ls[max(1, i-1)] * memo_ls[max(1, w-1-i)]
        if i < w-1:
            memo_ls3[j][i] += memo_ls3[j - 1][i + 1] * memo_ls[max(1, i)] * memo_ls[max(1, w-i-2)]
        memo_ls3[j][i] += memo_ls3[j-1][i] * memo_ls[max(1, i)] * memo_ls[max(1, w-i-1)]
        memo_ls3[j][i] %= MOD
print(memo_ls3[-1][k-1])

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(H: int, W: int, K: int):
    if W == 1:
        print(1)
        return 
    ## dp1[i][j] = H=１の時i->jに行く引き方
    ## 4→5と5→4の弾き方は同じ
    dp1 = [[0]*W for _ in range(W)]

    for i in range(2): 
        for j in range(W):
            # tmp[i][0] = iまでの見た時iに線引いてないものの総数
            # tmp[i][1] = iまでの見た時iに線引いているものの総数
            tmp = [[-1]*2 for _ in range(W-1)]
            if i == 0 or j == W-1: ## j -> j
                tmp[0][0] = 1
                if j == 0:
                    tmp[0][1] = 0
                else: ## 両隣にedgeがあってはいけない
                    if j != W-1: tmp[j][1] = 0
                    tmp[j-1][1] = 0
                    if tmp[0][1] != 0: tmp[0][1] = 1

                for k in range(0,W-2):
                    tmp[k+1][0] = tmp[k][0] + tmp[k][1] ## 前の幅に引いてても引いてなくてもいける
                    if tmp[k+1][1] == -1: 
                        tmp[k+1][1] = tmp[k][0] ## 前の幅に引いてない時のみいける。元々zeroが入ってたらパス
                
                dp1[j][j] = sum(tmp[-1])

            else: # j-> j+1
                if j == 0: 
                    tmp[0][1] = 1
                    tmp[0][0] = 0                    
                else:
                    tmp[j][0] = 0 ## jには絶対引いてなくてはならない
                    if j < W-2: tmp[j+1][1] = 0
                    tmp[j-1][1] = 0
                    if tmp[0][1] != 0:
                        tmp[0][1] = 1
                    tmp[0][0] = 1

                for k in range(0,W-2):
                    if tmp[k+1][0] == -1:
                        tmp[k+1][0] = tmp[k][0] + tmp[k][1] ## 前の幅に引いてても引いてなくてもいける
                    if tmp[k+1][1] == -1: 
                        tmp[k+1][1] = tmp[k][0] ## 前の幅に引いてない時のみいける。元々zeroが入ってたらパス
                dp1[j][j+1] = sum(tmp[-1])


    # dp2[h][w] = 高さhのときにw-1にいる弾き方の総数
    dp2 = [[0]*W for _ in range(H+1)]
    dp2[1] = dp1[0]
    for h in range(1,H):
        for k in range(W):
            if k >= 1 and k < W-1:
                dp2[h+1][k] = dp1[k-1][k]*dp2[h][k-1] + dp1[k][k]*dp2[h][k] + dp1[k][k+1]*dp2[h][k+1]
            elif k>=1:
                dp2[h+1][k] = dp1[k-1][k]*dp2[h][k-1] + dp1[k][k]*dp2[h][k]
            elif k <W-1:
                dp2[h+1][k] = dp1[k][k]*dp2[h][k] + dp1[k][k+1]*dp2[h][k+1]


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

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, K = [int(str) for str in input().strip().split()]

MOD = 1000000007

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

for h in range(H):
    for w in range(W):
        for bit in range(2 ** (W - 1)):
            if bit & (bit << 1):
                continue

            
            if w > 0 and bit & (1 << (w - 1)):
                dp[h + 1][w - 1] += dp[h][w]
                dp[h + 1][w - 1] %= MOD
            
            elif w < W - 1 and bit & (1 << w):
                dp[h + 1][w + 1] += dp[h][w]
                dp[h + 1][w + 1] %= MOD

            else:
                dp[h + 1][w] += dp[h][w]
                dp[h + 1][w] %= MOD

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