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 math
import sys
MOD = 1000000007

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

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

A = [[1]]


def bit(x, i):
    return (x >> i) & 1


def invalid(x):
    ans = False
    for j in range(w):
        if bit(x, j) == 1 and bit(x, j+1) == 1:
            ans = True
    return ans


for i in range(w-1):
    A[0].append(0)

for i in range(1, h+1):
    A.append([])
    for j in range(w):
        A[i].append(0)
    for x in range(2**(w-1)):
        if(invalid(x)):
            continue
        
        # corner case
        if bit(x, 0) == 1:
            A[i][0] = (A[i][0] + A[i-1][1]) % MOD
        else:
            A[i][0] = (A[i][0] + A[i-1][0]) % MOD
        if bit(x, w-2) == 1:
            A[i][w-1] = (A[i][w-1] + A[i-1][w-2]) % MOD
        else:
            A[i][w-1] = (A[i][w-1] + A[i-1][w-1]) % MOD
        
        for j in range(1, w-1):
            if bit(x, j-1) == 1:
                A[i][j] = (A[i][j] + A[i-1][j-1]) % MOD
            elif bit(x, j) == 1:
                A[i][j] = (A[i][j] + A[i-1][j+1]) % MOD
            else:
                A[i][j] = (A[i][j] + A[i-1][j]) % MOD

#print(A)

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()
mod = 1000000007

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

@lru_cache(maxsize=None)
def calc(n):
    """
    n個のものから隣り合わないように物をいくつか選択する場合の数(何も選ばないケースも許す)
    これは実はフィボナッチ数列になる
    """
    if n == -1: return 1
    if n == 0: return 1
    if n == 1: return 2
    return (calc(n - 1) + calc(n - 2)) % mod

@lru_cache(maxsize=None)
def func(h, w, k):
    if h == 0 and k == 1: return 1
    if h == 0: return 0
    if k == 1:
        val1 = func(h - 1, w, 1) * calc(w - 2) % mod
        val2 = func(h - 1, w, 2) * calc(w - 3) % mod
        return (val1 + val2) % mod
    if k == w:
        val1 = func(h - 1, w, w) * calc(w - 2) % mod
        val2 = func(h - 1, w, w - 1) * calc(w - 3) % mod
        return (val1 + val2) % mod
    val1 = func(h - 1, w, k - 1) * calc(k - 3) * calc(w - (k + 1)) % mod
    val2 = func(h - 1, w, k) * calc(k - 2) * calc(w - (k + 1)) % mod
    val3 = func(h - 1, w, k + 1) * calc(k - 2) * calc(w - (k + 2)) % mod
    return (val1 + val2 + val3) % mod

def main():
    H, W, K = map(int, input().split())
    if W == 1:
        print(1)
        return
    if W == 2:
        comb = Combination(H)
        if K == 1:
            ans = 0
            for i in range(H // 2 + 1): ans += comb(H, i * 2)
            print(ans)
        else:
            ans = 0
            for i in range(1, (H + 1) // 2 + 1): ans += comb(H, i * 2 - 1)
            print(ans)
        return
    print(func(H, W, K))
    

    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Number of Amidakuji

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

comb = []
def dfs(n, p):
    if len(n) == (W-1):
        if len(n) == 0:
            n = [0]
        comb.append(tuple(n))
        return
    for i in (0, 1):
        if p == 1 and i == 1:
            continue
        n.append(i)
        dfs(n, i)
        n.pop()  

dfs([], 0)

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        # まっすぐ降りてくるケース
        tmp = 0
        for i in comb:
            if w == 0 and i[w] == 0:
                tmp += 1
            elif w == (W-1) and i[w-1] == 0:
                tmp += 1
            elif i[w-1] == 0 and i[w] == 0:
                tmp += 1
        dp[h+1][w] += dp[h][w] * tmp

        # 左からくるケース
        if w != 0:
            tmp = 0
            for i in comb:
                if i[w-1] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w-1] * tmp        

        # 右からくるケース
        if w != (W-1):
            tmp = 0
            for i in comb:
                if i[w] == 1:
                    tmp += 1
            dp[h+1][w] += dp[h][w+1] * tmp  

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

Submission status: Accepted

Solution code:

from itertools import product


def patterns(w):
    res = []
    for pt in product([0, 1], repeat=w):
        valid = True
        for i in range(w - 1):
            if pt[i] == pt[i + 1] == 1:
                valid = False
                break
        if valid:
            res.append(pt)
    return res


def submit():
    h, w, k = [int(e) for e in input().split()]
    dp = [[0 for _ in range(w)] for _ in range(h + 1)]
    dp[0][0] = 1
    modp = 10 ** 9 + 7

    pts = patterns(w - 1)

    for i in range(1, h + 1):
        for j in range(w):
            for pt in pts:
                if j > 0 and pt[j - 1] == 1: # j -> j - 1に遷移する
                    dp[i][j - 1] += dp[i - 1][j]
                    dp[i][j - 1] %= modp
                elif j < w - 1 and pt[j] == 1:  # j -> j + 1に遷移する
                    dp[i][j + 1] += dp[i - 1][j]
                    dp[i][j + 1] %= modp
                else:
                    dp[i][j] += dp[i - 1][j]
                    dp[i][j] %= modp


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


submit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,K=map(int,input().split())
    dpdp=[[0]*2 for _ in range(W)]
    dpdp[0][0]=1
    for i in range(W-1):
        dpdp[i+1][0]=dpdp[i][0]+dpdp[i][1]
        dpdp[i+1][1]=dpdp[i][0]
    
    dp=[[0]*W for _ in range(H+1)]
    dp[0][0]=1
    for i in range(H):
        for j in range(W):
            if j==0 or j==W-1:
                dp[i+1][j]+=dp[i][j]*(sum(dpdp[W-2]))
            else:
                dp[i+1][j]+=dp[i][j]*(sum(dpdp[max(j-1,0)])*sum(dpdp[max(W-2-j,0)]))
            dp[i+1][j]%=MOD
            if j<=W-2:
                dp[i+1][j+1]+=dp[i][j]*(sum(dpdp[max(j-1,0)])*sum(dpdp[max(W-3-j,0)]))
                dp[i+1][j+1]%=MOD
            if j>=1:
                dp[i+1][j-1]+=dp[i][j]*(sum(dpdp[max(j-2,0)])*sum(dpdp[max(W-2-j,0)]))
                dp[i+1][j-1]%=MOD
    print(dp[-1][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 _ in range(h+1)]
dp[0][0] = 1

for i in range(1, h+1):
    for j in range(w):
        left, center, right = 0, 0, 0

        for k in range(2**(w-1)):
            invalid = False
            for l in range(1, w-1):
                if k >> l & 1 and k >> (l-1) & 1:
                    invalid = True

            if invalid:
                continue

            no_line = True

            if j > 0:
                if k >> (j-1) & 1:
                    left += 1
                    no_line = False

            if j < w-1:
                if k >> j & 1:
                    right += 1
                    no_line = False

            if no_line:
                center += 1

        if j > 0:
            dp[i][j] += dp[i-1][j-1] * left

        if j < w-1:
            dp[i][j] += dp[i-1][j+1] * right

        dp[i][j] += dp[i-1][j] * center
        dp[i][j] %= mod

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

Submission status: Accepted

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

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

possible = []
for i in range(1<<(W-1)):
  b = bin(i)[2:]
  flag = 1
  for j in range(len(b)-1):
    if b[j] == b[j+1] == "1":
      flag = 0
  if flag:
    possible.append(int(b,2))

def amida(b):
  ret = [i for i in range(W)]
  for i in range(W-1):
    if b>>i & 1:
      ret[i],ret[i+1] = ret[i+1],ret[i]
  return ret

ans = [0 for i in range(W)]
ans[0] = 1

for _ in range(H):
  new_ans = [0 for i in range(W)]
  for b in possible:
    for i in range(W):
      new_ans[i] = (new_ans[i] + ans[amida(b)[i]])%MOD
  ans = new_ans
  
print(ans[K-1])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def bit_count(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

H,W,K = inputIL()

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

possible = []
for i in range(1<<(W-1)):
  b = bin(i)[2:]
  flag = 1
  for j in range(len(b)-1):
    if b[j] == b[j+1] == "1":
      flag = 0
  if flag:
    possible.append(int(b,2))

def amida(b):
  ret = [i for i in range(W)]
  for i in range(W-1):
    if b>>i & 1:
      ret[i],ret[i+1] = ret[i+1],ret[i]
  return ret

ans = [0 for i in range(W)]
ans[0] = 1


for _ in range(H):
  new_ans = [0 for i in range(W)]
  for b in possible:
    for i in range(W):
      new_ans[i] = (new_ans[i] + ans[amida(b)[i]])%MOD
  ans = new_ans
  
print(ans[K-1])

Submission status: Accepted

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

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

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

DP[0][K] = 1
for i in range(1, H + 1):
    for j in range(W):
        DP[i][j] = DP[i-1][j] * (Hikikata[j-1] * Hikikata[W-j-2]) % mod + DP[i-1][j-1] * (Hikikata[j-2] * Hikikata[W-j-2]) % mod + DP[i-1][j+1] * (Hikikata[j-1] * Hikikata[W-j-3]) % mod
        DP[i][j] %= mod

print(DP[H][0])

Submission status: Accepted

Solution code:
import sys

def comb(n, r, mod=None):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    ans = 1
    for i in range(1, r+1):
        if mod:
            x *= n+1-i
            y *= i
            x %= mod
            y %= mod
        else:
            ans *= n+1-i
            ans //= i
    ans = x*pow(y, mod-2, mod)%mod if mod else ans
    return ans


def main():
    h, w, k = map(int, input().split())
    mod = pow(10,9)+7
    
    if w == 1:
        print(1)
        sys.exit()
    
    comb_list = [[0]*11 for _ in range(11)]
    for i in range(11):
        for j in range(11):
            if i >= j:
                comb_list[i][j] = comb(i, j)
    
    key_list = [1]*10
    for i in range(1, 10):
        key = 0
        for j in range(1, 10):
            if i < j*2-1:
                break
            key += comb_list[i-j+1][j]
        key_list[i] += key
    
    
    dp = [[0]*w for _ in range(h)]
    for i in range(h):
        if i == 0:
            dp[0][0] = key_list[w-2]
            dp[0][1] = key_list[w-3] if w != 2 else 1
            continue
        if w == 2:
            dp[i][0] = (dp[i-1][0]+dp[i-1][1])%mod
            dp[i][1] = (dp[i-1][0]+dp[i-1][1])%mod
            continue
            
        for j in range(w):
            if j == 0:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j+1]*key_list[w-3])%mod
            elif j == w-1:
                dp[i][j] = (dp[i-1][j]*key_list[w-2]+dp[i-1][j-1]*key_list[w-3])%mod
            else:
                dp[i][j] = 0
                dp[i][j] += (dp[i-1][j-1]*key_list[max([0, j-2])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j]*key_list[max([0, j-1])]*key_list[max([0, w-2-j])])%mod
                dp[i][j] += (dp[i-1][j+1]*key_list[max([0, j-1])]*key_list[max([0, w-3-j])])%mod
                dp[i][j] %= mod
    print(dp[h-1][k-1])
                                                                           

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools


def amida_patterns(w):
    # (0, 1, 2, ... , w - 1) -> ?
    ret = list()
    for bars in itertools.product([0, 1], repeat=w-1):
        if sum([b * bb for b, bb in zip(bars[1:], bars[:-1])]) > 0:
            continue
        location = list(range(w))
        for i in range(w):
            if i > 0 and bars[i - 1] == 1:
                location[i] = i - 1
            elif i < w - 1 and bars[i] == 1:
                location[i] = i + 1
        ret.append(location)
    return ret


def main():
    MOD = 10**9 + 7
    H, W, K = list(map(int, input().split(' ')))
    ap_list = amida_patterns(W)
    dp = [[0 for _ in range(W)] for _ in range(H + 1)]
    dp[0][0] = 1
    for h in range(1, H + 1):
        for a in ap_list:
            for w in range(W):
                dp[h][a[w]] += dp[h - 1][w]
                dp[h][a[w]] %= MOD
    print(dp[H][K - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

h, w, k = map(int, input().split())
mod = 10 ** 9 + 7

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


def check_valid_bridge(bridge):
    for i in range(1, w-1):
        if bridge[i-1] and bridge[i]:
            return False
    return True

for t in range(1, h + 1):
    for i in range(1, w + 1):
        X, Y, Z = 0, 0, 0
        if w != 1:
            p = product([True, False], repeat=w-1)            
            for bridge in p:
                if check_valid_bridge(bridge):
                    if i > 1 and bridge[i-2]:
                        X += 1
                    elif i < w and bridge[i-1]:
                        Y += 1
                    elif (i == 1 and not bridge[i-1]) or (i == w and not bridge[i-2]) or (1 < i < w and not bridge[i-2] and not bridge[i-1]):
                        Z += 1
        else:
            Z = 1
        # print(f"{X} {Y} {Z}")
        pattern_1 = dp[t-1][i-1] * X if i > 1 else 0
        pattern_2 = dp[t-1][i+1] * Y if i < w else 0
        pattern_3 = dp[t-1][i] * Z
        dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

# for line in dp:
#     print(*line)
print(dp[h][k])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().rstrip().split())
    K -= 1
    dp = [[0] * W 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)):
                b = bin(k)[2:].zfill(W-1)
                # 近接する2つの横線がつながってるか判定
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    # 左方向に横線を辿るケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[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])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().rstrip().split())
    # K -= 1
    dp = [[0] * W 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)):
                b = bin(k)[2:].zfill(W-1)
                # 2つの横線がつながってないか調べる
                flg = True
                for l in range(W-2):
                    if b[l] == b[l+1] == '1':
                        flg = False
                        break
                if not flg:
                    continue
                if j >= 1 and b[j-1] == '1':
                    # 左方向に横線を辿るケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and b[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])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
inf = 10**15
mod = 10**9+7

h,w,k = list(map(int, input().split()))
# 高さiの時jにいる通り
dp = [[0 for j in range(w+1)]for i in range(h+1)]
dp[0][1] = 1
for i in range(h):
    for x in range(2**(w-1)):
        flag = True
        count = 0
        tmp = x
        for l in range(w-1):
            if ((tmp >> l) & 1):
                count+=1
                if count == 2:
                    flag = False
            else:
                count=0
        if flag:
            zeroflag = True
            for j,y in enumerate(range(w-1)):
                if ((x >> y) & 1):  # 1だったら(オンだったら)
                    dp[i+1][j+1] += dp[i][j+2]
                    dp[i+1][j+2] += dp[i][j+1]
                    zeroflag = False
                else:
                    if zeroflag:
                        dp[i+1][j+1] += dp[i][j+1]
                    else:
                        zeroflag = True
            if zeroflag:
                dp[i+1][-1] += dp[i][-1]
    for g in range(1,w+1):
        dp[i+1][g] = dp[i+1][g] % mod
print(dp[h][k])

Submission status: Accepted

Solution code:
fib = [1, 1, 2, 3, 5, 8, 13, 21]
mod = 1000000007
h, w, k = map(int, input().split())
k -= 1
p = [0] * w
p[0] = 1
for i in range(h):
  q = [0] * w
  for j in range(w):
    if j > 0:
      q[j] += p[j - 1] * fib[j - 1] * fib[w - 1 - j]
    if j < w - 1:
      q[j] += p[j + 1] * fib[j] * fib[w - j - 2]
    if 0 < j < w - 1:
      q[j] += p[j] * fib[j] * fib[w - j - 1]
    elif j > 0:
      q[j] += p[j] * fib[j]
    elif j < w - 1:
      q[j] += p[j] * fib[w - j - 1]
    else:
      q[j] += p[j]
    q[j] %= mod
  p = q
print(p[k])

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
#a(h,x)
p=[-1]*(w+1)
p[0]=1
p[1]=2
def pat(x):
    if x<0 or x>=w:
        return 1
    else:
        if p[x]!=-1:
            return p[x]
        else:
            p[x]=pat(x-2)+pat(x-1)
            return p[x]
        
for j in range(1):
    0
mo=10**9 +7

a=[[0 for i in range(w)] for i in range(h+1)]
a[0]=[1]+[0]*(w-1)
for i in range(1,h+1):
    #a[i][0]=a[i-1][0]*pat(-1)*pat(h-1)+a[i-1][1]*pat(0)*pat(h-2)
    #a[i][w-1]=a[i-1][w-2]*pat(w-3)*pat(h-w+1)+a[i-1][w-1]*pat(w-1-1)*pat(h-w)
    for j in range(0,w):
        if j>0: a[i][j]+=a[i-1][j-1]*pat(j-2)*pat(w-j-2)
        a[i][j]+=a[i-1][j]*pat(j-1)*pat(w-1-j-1)
        if j<w-1: a[i][j]+=a[i-1][j+1]*pat(j-1)*pat(w-j-3)
print(a[h][k-1] % mo)
#print(a)

Submission status: Accepted

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

dp = [[0] * 8 for _ in range(H + 1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        dp[h + 1][w] = dp[h][w] * h_lines[w] * h_lines[W - w - 1]
        if w > 0:
            dp[h + 1][w] += dp[h][w - 1] * h_lines[w - 1] * h_lines[W - w - 1]
        if w < W - 1:
            dp[h + 1][w] += dp[h][w + 1] * h_lines[w] * h_lines[W - w - 2]
        dp[h + 1][w] %= MOD
print(dp[H][K - 1])

Submission status: Accepted

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

try:
    from typing import List, Tuple
except ImportError:
    pass


MOD = 1000000007  # type: int


def isvalid(ptn: "Tuple[bool]"):
    return not any(h1 and h2 for h1, h2 in zip(ptn, ptn[1:]))


def solve(H: int, W: int, K: int):
    validptns = [
        ptn
        for ptn in product((False, True), repeat=W - 1)
        if isvalid(ptn)
    ]  # type: List[Tuple[bool]]
    dp = [1 if i == K - 1 else 0 for i in range(W)]  # type: List[int]
    for _ in range(H):
        newdp = [0] * W  # type: List[int]
        for ptn in validptns:
            for s in range(W):
                t = s
                if s < W - 1 and ptn[s]:
                    t = s + 1
                elif s > 0 and ptn[s - 1]:
                    t = s - 1
                newdp[t] += dp[s]
                newdp[t] %= MOD
        dp = newdp

    print(dp[0])


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
MOD=10**9+7


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

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

dp[0][0]=1

#初期値が0の辞書
zentan1=[0]*(w-1)
zentan2=[0]*(w)

for i in range(2**(w-1)):
    if "11" not in str(bin(i)):
        
        s=(str(bin(i))[2:]).zfill(w-1)
        for index,ss in enumerate(s):        
            #print(index,ss)
            if ss=="1":
                zentan1[index]+=1
            else:
                if index==0:
                    zentan2[index]+=1
                elif index==len(s)-1:
                    zentan2[index+1]+=1
                    if s[index-1]=="0":
                        zentan2[index]+=1
                else:
                    if s[index-1]=="0":
                        zentan2[index]+=1
        #print(zentan1)
        #print(zentan2)






        """
        j=0
        while j<w-1:
            #print(j)
            if i>>j & 1:
                #print(j)
                zentan1[j]+=1
            j+=1
        """

#print("11",zentan1)
#print("00",zentan2)

for i in range(1,h+1):
    x=0
    while x<w:
        for index,mv in enumerate([-1,0,1]):
            if 0<= x+mv < w:
                if index==1:
                    dp[i][x]+=dp[i-1][x+mv]*zentan2[x]
                elif index==0:
                    dp[i][x]+=dp[i-1][x+mv]*zentan1[x-1]
                elif index==2:
                    dp[i][x]+=dp[i-1][x+mv]*zentan1[x]

        x+=1
    #print(dp[i])
print(dp[h][k-1]%MOD)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    if W == 1:
        print(1)
        return

    cnt = [0] * (W - 1)
    cntz = [0] * W
    for i in range(2 ** (W - 1)):
        tmp = [0] * (W - 1)
        for j in range(W - 1):
            if i >> j & 1:
                tmp[j] += 1
        # 2辺連続で引かれていないかをチェック
        for j, k in zip(tmp, tmp[1:]):
            if j == k == 1:
                break
        else:
            # チェックをパスした状態をカウント
            for j in range(W - 1):
                cnt[j] += tmp[j]
            for j in range(W):
                if j == 0:
                    if tmp[j] == 0:
                        cntz[j] += 1
                elif j == W - 1:
                    if tmp[j - 1] == 0:
                        cntz[j] += 1
                else:
                    if tmp[j] == tmp[j - 1] == 0:
                        cntz[j] += 1

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

    for j in range(H):
        for i in range(W):
            if i == 0:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
            elif i == W - 1:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i - 1] %= MOD
            else:
                dp[j + 1][i] += dp[j][i] * cntz[i]
                dp[j + 1][i + 1] += dp[j][i] * cnt[i]
                dp[j + 1][i - 1] += dp[j][i] * cnt[i - 1]
                dp[j + 1][i] %= MOD
                dp[j + 1][i + 1] %= MOD
                dp[j + 1][i - 1] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC113-D Number of Amidakuji
"""
問題：
W本長さHの棒に任意に横線を引く時に、
1からスタートしてkにたどり着くあみだくじの通り数を求めよ
ただし、横線には以下の制約がある
同じ高さに何本引いても良いが、その端点が隣接してはいけない
同じ高さ同士にしか引けない
隣り合う棒にしか引けない
解法：
dpを用いて解く。
dp[i][j]:高さiの状態にいる時の、棒jにたどり着く通り数
dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]の三通りの遷移について、
(これは横線は必ず端点を共有しないことから言える)
それぞれあり得る通り数を全探索して足していった結果が答え。
最終的にd[h][k]が答え
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
h,w,g = map(int,readline().split())

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

def func(x):
    if x <= 0:
        return 1
    return func(x-2) + func(x-1)

for i in range(h):
    for j in range(w):
        for k in range(-1,2): #左下、直下、右下
            if not 0 <= j + k < w:
                continue
            #func:右側,左側の自由な状態の棒間の数を入れてやる
            if k == -1:
                l = max(0,j-2)
                r = max(0,w-1-(j+1))
            elif k == 0:
                l = max(0,j-1)
                r = max(0,w-1-(j+1))
            else:
                l = max(0,j-1)
                r = max(0,w-1-(j+2))
            dp[i+1][j+k] += dp[i][j]*func(l)*func(r)
            dp[i+1][j+k] %= mod


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

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[i][j]:=端点iまで辺を張った時辺ｊにたどり着くあみだくじの数
dp[0][0]=1
for hi in range(1,h+1):
    for i in range(2**(w-1)):
        idx1=[]
        idx2=[]
        ok=True
        for j in range(w-1):
            if (i>>j)&1:
                idx1.append(j)
                idx2.append(j)
                idx2.append(j+1)
        if len(idx1)>=2:
            for j in range(len(idx1)-1):
                if idx1[j+1]==idx1[j]+1:
                    ok=False
        if not ok:
            continue
        idx1=set(idx1)
        idx2=set(idx2)
        for wi in range(w):
            if wi in idx1:
                dp[hi][wi]+=dp[hi-1][wi+1]
                dp[hi][wi+1]+=dp[hi-1][wi]
                dp[hi][wi]%=mod
                dp[hi][wi+1]%=mod
            if wi not in idx2:
                dp[hi][wi]+=dp[hi-1][wi]
                dp[hi][wi]%=mod
print(dp[h][k-1])