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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    x, y = LI()
    print(x+y//2)
    return

#B
def B():
    II()
    t, a = LI()
    h = LI()
    ans = [0,inf]
    for num, i in enumerate(h):
        if ans[1] > abs(t - a - i * 0.006):
            ans = [num, abs(t - a - i * 0.006)]
    print(ans[0] + 1)
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    h, w, k = LI()
    stick = [[0, 0] for i in range(w)]
    stick[0] = [1, 0]
    for i in range(1, w):
        stick[i][0] += stick[i - 1][0] + stick[i - 1][1]
        stick[i][1] += stick[i - 1][0]
    dp1 = [0] * (w + 2)
    dp1[1] = 1
    for i in range(h):
        dp2 = [0] * (w + 2)
        for wi in range(1, w + 1):
            tmp = dp1[wi - 1] * stick[wi - 1][1] * stick[w - wi][0]
            tmp += dp1[wi + 1] * stick[w - wi][1] * stick[wi - 1][0]
            tmp += dp1[wi] * stick[wi - 1][0] * stick[w - wi][0]
            dp2[wi] = tmp
            dp2[wi] %= mod
        dp1 = dp2
    print(dp2[k])

    return

#Solve
if __name__ == '__main__':
    D()

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
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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



def fib(n):
    a, b = 1, 1
    fib_list = [1] * n
    for i in range(n - 2):
        a, b = a + b, a
        fib_list[i + 2] = a
    return fib_list



h, w, k = LI()
L = [0] + fib(w + 1)
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 - 1] = (dp[i + 1][j - 1] + dp[i][j] * L[j] * L[w - j]) % mod
        if j + 1 < w:
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * L[j + 1] * L[w - j - 1]) % mod
        dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * L[j + 1] * L[w - j]) % mod



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

Submission status: Accepted

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

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

    dp[0][0] = 1
    MOD = 10**9 + 7

    for h in range(H):
        for j in range(1 << W-1):
            a = str(bin(j))[2:].zfill(W-1)
            if a.count('11') >= 1:
                continue
            for w in range(W):
                if w == 0:
                    # まっすぐ移動
                    if a[w] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    # 右へ移動
                    if a[w] == '1':
                        dp[h+1][w+1] += dp[h][w]
                        dp[h+1][w+1] %= MOD
                elif w == W-1:
                    # まっすぐ移動
                    if a[w-1] == '0':
                        dp[h+1][w] += dp[h][w]
                        dp[h+1][w] %= MOD
                    # 左へ移動
                    if a[w-1] == '1':
                        dp[h+1][w-1] += dp[h][w]
                        dp[h+1][w-1] %= 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])

                
main()

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    
    if W == 1:
        print(1)
        exit()

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

    for h in range(H):
        # 1: 線あり、 0: 線なし
        for i in range(2 ** (W-1)):
            # 連続した1がある→隣接する列に線が引かれている
            if bin(i).count('11') >= 1:
                continue
            perm = [k for k 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):
                dp[h+1][perm[j]] += dp[h][j]
                dp[h+1][perm[j]] %= MOD

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



main()

Submission status: Accepted

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

dp = [0] * W
pp = [0] * W

dp[0] = 1

for h in range(1,H+1):
    dp, pp = pp, dp
    dp = [0] * W
    # 一行における横棒のパターンを全探索
    for bs in product((0,1), repeat=W-1):
        swaps = []
        throughs = []
        # validity check and swap or through
        valid = True
        for i in range(1,W-1):
            if bs[i] == bs[i-1] == 1:
                valid = False
                break
        if not valid:
            continue
        for i in range(W-1):
            if bs[i]:
                swaps.append((i,i+1))
            else:
                if len(swaps) == 0 or swaps[-1][-1] != i:
                    throughs.append(i)
        if len(swaps) == 0 or swaps[-1][-1] != W-1:
            throughs.append(W-1)
        for s in swaps:
            dp[s[0]] += pp[s[1]]
            dp[s[1]] += pp[s[0]]
            dp[s[0]] %= MOD
            dp[s[1]] %= MOD
        for t in throughs:
            dp[t] += pp[t]
            dp[t] %= MOD

print(dp[K-1])

Submission status: Accepted

Solution code:
H,W,K = [int(x) for x in input().split()]
dp=[[0]*W for _ in range(H+1)]
dp[0][0]=1
for i in range(H):
  for j in range(W):
    for bit in range(1<<(W-1)):
      flag = 1
      for k in range(W-2):
        if (bit&1<<k) and (bit&1<<k+1):
          flag = 0
      if flag!=1:
        continue
      nj = j
      if (bit&1<<j):
        nj = 1+j
      if j>0 and (bit&1<<(j-1)):
        nj = j-1
      dp[i+1][nj] +=dp[i][j]
      dp[i+1][nj] %=(10**9+7)
print(dp[H][K-1])

Submission status: Accepted

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

Submission status: Accepted

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

def swap(l, a, b):
    # print("s", a, b)
    l[a], l[b] = l[b], l[a]

def check_row(m):
    l = list(range(W))
    b = 0
    for i in range(W-1):
        c = (m>>i)%2
        # print(b, c)
        if b == c == 1:
            return False
        if c == 1:
            swap(l, i, i+1)
        b = c
    return l


# i行目までで1がjにいる組み合わせの数
dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1

for i in range(1, H+1):
    for j in range(1<<(W-1)):
        r = check_row(j)
        if r == False:
            continue
        # print(r)
        for k, r_i in enumerate(r):
            # print(i, k, r_i)
            dp[i][r_i] = (dp[i][r_i] + dp[i-1][k]) % (10**9+7)

# print(*dp, sep="\n")
print(dp[H][K-1])

Submission status: Accepted

Solution code:
H,W,K = map(int, input().split())
# HとWは道の数を決定
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          # 二桁連続で1の場合は処理を省く
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        #print('pre',dp[i])
        #print(dp[i+1])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
mod = 1000000007
dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][1]=1
for i in range(1,H+1):
    for j in range(1,W+1):
        x=0
        y=0
        z=0
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=2 and tmp[j-2] != "1"):
                    Flag = False
                    break
            if Flag:
                x+=1
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=2 and tmp[j-2] == "1") or (j>=1 and tmp[j-1] == "1"):
                    Flag = False
                    break
            if Flag:
                y+=1   
        for k in range(2**(W-1)):
            tmp = format(k, "b")
            tmp = tmp.zfill(W-1)
            tmp += "0"
            tmp = list(tmp)
            Flag = True
            for l in range(len(tmp)-1):
                if tmp[l] == tmp[l+1] == "1" or (j>=1 and tmp[j-1] != "1"):
                    Flag = False
                    break
            if Flag:
                z+=1   
        dp[i][j] += x*dp[i-1][j-1]+y*dp[i-1][j]+z*dp[i-1][j+1]
        dp[i][j] %= mod
print(dp[H][K]%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
H, W, K = map(int, input().split())
table = [[0, 0, 0] for i in range(9)]

for i in range(2**(W-1)):
    n = [i & 2**j for j in range(8)]
    for i in range(7):
        if n[i] and n[i+1]:#真横にかかるとき
            break
    else:
        i = 0
        while i < W:
            if not n[i]:
                table[i+1][1] += 1
                i += 1
            else:
                table[i+1][2] += 1
                table[i+2][0] += 1
                i += 2
dp = [[0 for i in range(W+2)] for j in range(H+1)]
dp[0][1] = 1

for i in range(1, H+1):
    for j in range(1, W+1):
        a = dp[i-1][j-1] * table[j][0]
        b = dp[i-1][j] * table[j][1]
        c = dp[i-1][j+1] * table[j][2]
        dp[i][j] = (a+b+c) % MOD
print(dp[H][K])

Submission status: Accepted

Solution code:
height, width, k = map(int, input().split())

start_w = 1
end_w = width

if end_w <= 1:
    print(1)
    exit()


def enum_no_relation_cases(n, m=0):
    front = n - (start_w + 1) - (m * (m - 1)) // 2
    rear = end_w - (n + 1) - (m * (m + 1)) // 2
    return int(enum_amida_all_cases(front) * enum_amida_all_cases(rear))


def enum_amida_all_cases(n):
    if n < 1:
        return 1
    return fibonacci(n + 2)


f = [1, 1, 1] + ([0] * (end_w - 1))


def fibonacci(n):
    if f[n] == 0:
        f[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return f[n]


ans = [[0] * (1 + end_w + 1) for i in range(height + 1)]
ans[0][start_w] = 1
search_range = start_w + 1
for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        from_just_above = ans[h - 1][w] * enum_no_relation_cases(w)
        from_upper_left = ans[h - 1][w - 1] * enum_no_relation_cases(w, -1)
        from_upper_right = ans[h - 1][w + 1] * enum_no_relation_cases(w, 1)
        ans[h][w] = from_just_above + from_upper_left + from_upper_right

    if search_range < end_w:
        search_range += 1

print(ans[height][k] % 1000000007)

Submission status: Accepted

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

if w == 1:
    print(1)
else:
    acr = []
    for p in range(2**(w-1)):
        det = 0
        pp = p
        exist = [0] * (w-1)
        for i in range(w-1):
            exist[i] = pp % 2
            pp = pp // 2
        for ii in range(w-2):
            if exist[ii] == 1 and exist[ii+1] == 1:
                det = 1
        if det == 0:
            acr.append(exist[:])
    #print(acr)

    cur = [0] * w
    cur[0] = 1
    

    for t in range(h):
        n = [0] * w
        for x in range(len(acr)):
            n[0] = (n[0] + cur[1] * acr[x][0] + cur[0] * (1-acr[x][0]))%MOD
            for j in range(1,w-1):
                n[j] = (n[j] + cur[j-1] * acr[x][j-1] + cur[j+1] * acr[x][j] + cur[j] * (1-acr[x][j-1])*(1-acr[x][j]))%MOD
            n[w-1] = (n[w-1] + cur[w-2] * acr[x][w-2] + cur[w-1] * (1-acr[x][w-2])) % MOD
        
        cur = n[:]
        
    print(cur[k-1])

Submission status: Accepted

Solution code:
def main():
    MOD = 1000000007
    
    H, W, K = map(int, input().split())
    table = [[0, 0, 0] for i in range(9)]
    
    for i in range(2**(W-1)):
        n = [i & 2**j for j in range(8)]
        
        for i in range(7):
            if n[i] and n[i+1]:
                break
        else:
            i = 0
            while i < W:
                if not n[i]:
                    table[i+1][1] += 1
                    i += 1
                else:
                    table[i+1][2] += 1
                    table[i+2][0] += 1
                    i += 2
                    
    dp = [[0 for i in range(W+2)] for j in range(H+1)] 
    dp[0][1] = 1
    
    for i in range(1, H+1):
        for j in range(1, W+1):
            a = dp[i-1][j-1] * table[j][0]
            b = dp[i-1][j] * table[j][1]
            c = dp[i-1][j+1] * table[j][2]
            dp[i][j] = (a+b+c) % MOD
        
    print(dp[H][K])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import itertools
    mod = 10**9+7
    H,W,K = map(int, input().split())
    zero = [0,1]
    dp = [[[0]*W for i in range(W)] for j in range(H+1)]
    for i in range(W):
        dp[0][i][i] = 1
    #print(dp)
    for h in range(1,H+1):
        
        for v in itertools.product(zero, repeat = W-1):
            flag = 0
            for i in range(len(v)-1):
                if v[i] == v[i+1] == 1:
                    flag = 1
            if flag == 0:
                goto = []
                for i in range(W):
                    goto.append(i)
                for i in range(len(v)):
                    if v[i] == 1:
                        tmp = goto[i]
                        goto[i] = goto[i+1]
                        goto[i+1] = tmp
                #print(goto)        
                for i in range(W):
                    for j in range(W):
                        dp[h][i][goto[j]] += dp[h-1][i][j]
                        dp[h][i][goto[j]] %= mod
        #print(dp)
    print(dp[H][0][K-1])
            
    
main()

Submission status: Accepted

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

ck = [0]*9
ck[0] = 1
for i in range(1,9):
  for j in range(2**(i-1)):
    for k in range(i-1):
      if (j>>k)&(j>>(k+1))==True:
        break
    else:
      ck[i] += 1

mod = 10**9+7
for i in range(1,H+1):
  for j in range(W):
    if (j == 0)&(j == W-1):
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == 0:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])
    elif j == W-1:
      dp[i][j] = dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])
    else:
      dp[i][j] = dp[i-1][j+1]*(ck[j]*ck[W-j-2])+dp[i-1][j]*(ck[j]*ck[W-1-j])+dp[i-1][j-1]*(ck[j-1]*ck[W-j-1])

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

Submission status: Accepted

Solution code:
# 愚直にやったけど、もうちょいよい方法はないものか
def genP(W):
    P = []
    D = [0]*(W-1)
    P.append(D[:])
    for i in range(2**(W-1)-1):
        d = 0
        while D[d] == 1:
            D[d] = 0
            d+=1
        D[d] = 1
        if any(D[i] == 1 and D[i+1] == 1 for i in range(W-2)):
            continue
        P.append(D[:])
    return P 

# ここがちょっと煩雑
def make_swap(p, W):
    base = [x for x in range(0,W)]
    b = base[:] 
    for w in range(len(p)):
        if p[w] == 1:
            b[w], b[w+1] = b[w+1], b[w]
    return b


def solve(H, W, K):
    swaps = []
    for p in genP(W):
        s = make_swap(p, W)
        swaps.append(s)

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

    for h in range(0,H):
        for w in range(0, W):
            for swap in swaps:
                count[h+1][w] += count[h][swap[w]]
                count[h+1][w] %= 1000000007
    #print(count[H])
    print(count[H][K-1])

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

Submission status: Accepted

Solution code:
def genP(W):
    P = []
    D = [0]*(W-1)
    P.append(D[:])
    for i in range(2**(W-1)-1):
        d = 0
        while D[d] == 1:
            D[d] = 0
            d+=1
        D[d] = 1
        if any(D[i] == 1 and D[i+1] == 1 for i in range(W-2)):
            continue
        P.append(D[:])
    return P 

def make_swap(p, W):
    base = [x for x in range(0,W)]
    b = base[:] 
    for w in range(len(p)):
        if p[w] == 1:
            b[w], b[w+1] = b[w+1], b[w]
    return b

if 0==1:
    W = 4
    base = [x-1 for x in range(1,W+1)]
    for p in genP(W):
        print(*base)
        print("", *p)
        print(*make_swap(p, W))
        print()

def solve(H, W, K):
    swaps = []
    for p in genP(W):
        s = make_swap(p, W)
        swaps.append(s)

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

    for h in range(0,H):
        for w in range(0, W):
            for swap in swaps:
                count[h+1][w] += count[h][swap[w]]
                count[h+1][w] %= 1000000007
    #print(count[H])
    print(count[H][K-1])

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

Submission status: Accepted

Solution code:
F = [1, 1]
for i in range(7):
  F.append(F[i]+F[i+1])

h, w, k = map(int, input().split())
mod = 10**9 + 7
a = [[0 for i in range(w)] for i in range(h+1)]
a[0][0] = 1

if w == 1:
  print(1)
else:
  for i in range(h):
    for j in range(w):
      if j == 0:
        a[i+1][j] += F[w-1] * a[i][j] % mod
        a[i+1][j+1] += F[w-2] * a[i][j] % mod
      elif j==w-1:
        a[i+1][j] += F[w-1] * a[i][j] % mod
        a[i+1][j-1] += F[w-2] * a[i][j] % mod
      else:
        a[i+1][j] += F[j] * F[w-j-1] * a[i][j] % mod
        a[i+1][j+1] += F[j] * F[w-j-2] * a[i][j] % mod
        a[i+1][j-1] += F[j-1] * F[w-j-1] * a[i][j] % mod
        
  print(a[-1][k-1]%mod)

Submission status: Accepted

Solution code:
def calc(num):
    a, b, c = 0, 0, 0
    for i in range(2 ** (w - 1)):
        kk = 0
        kkk = 0
        t = "0" * (w - 1 - len(bin(i)[2:])) + bin(i)[2:]
        if ("11" not in t):
            if (num <= w - 2):
                if (t[num] == "1"):
                    c += 1
                    kk = 1
            if (num - 1 >= 0):
                if (t[num - 1] == "1"):
                    b += 1
                    kkk = 1
            if (kk + kkk) == 0:
                a += 1
    return a, b, c


h, w, k = map(int, input().split())
k -= 1
mod = (10 ** 9) + 7
dp = [[0 for _ in range(w)] for _ in range(h + 1)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        a, b, c = calc(j)
        dp[i + 1][j] = ((dp[i][j] * a) + dp[i + 1][j]) % mod
        if j - 1 >= 0:
            dp[i + 1][j - 1] = ((dp[i][j] * b) + dp[i + 1][j - 1]) % mod
        if j + 1 < w:
            dp[i + 1][j + 1] = ((dp[i][j] * c) + dp[i + 1][j + 1]) % mod
print(dp[h][k])

Submission status: Accepted

Solution code:

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

amari = [1,1,2,3,5,8,13,21]

lis = [0] * W

lis[0] += 1

for j in range(H):

    nlis = [0] * W

    for i in range(W):

        if i > 0:

            if i == 1:
                nlis[i-1] += lis[i] * amari[W-2]

            else:
                nlis[i-1] += lis[i] * amari[i-1] * amari[W-1-i]

        nlis[i] += lis[i] * amari[i] * amari[W-1-i]

        if i < W-1:

            if i == W-2:
                nlis[i+1] += lis[i] * amari[W-2]

            else:
                nlis[i+1] += lis[i] * amari[i] * amari[W-i-2]

    for i in range(W):

        lis[i] = nlis[i] % (10 ** 9+ 7)

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

Submission status: Accepted

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

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

B = [format(i, 'b').zfill(W - 1) for i in range(2 ** (W - 1)) if '11' not in format(i, 'b')]

for h in range(H):
  for w in range(W):
    for b in B:
      if w > 0 and b[w - 1] == '1':
      	dp[h + 1][w - 1] += dp[h][w]
      elif w < W - 1 and b[w] == '1':
        dp[h + 1][w + 1] += dp[h][w]
      else:
        dp[h + 1][w] += dp[h][w]

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

Submission status: Accepted

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

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

B = [i for i in range(2 ** (W - 1)) if '11' not in format(i, 'b')]

for h in range(H):
  for w in range(W):
    for b in B:
      if w > 0 and (b >> (w - 1)) & 1:
      	dp[h + 1][w - 1] += dp[h][w]
      elif w < W - 1 and (b >> w) & 1:
        dp[h + 1][w + 1] += dp[h][w]
      else:
        dp[h + 1][w] += dp[h][w]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for _ in range(h)]
D=[[0]*w for _ in range(w)]
for i in range(2**(w-1)):
    s='0'+bin(i)[2:].rjust(w-1,'0')+'0'
    if '11' in s:continue
    for i in range(w-1):
        if s[i+1]=='1':
            D[i][i+1]+=1
            D[i+1][i]+=1
    for i in range(w):
        if s[i:i+2]=='00':
            D[i][i]+=1
dp[0]=D[0]
for i in range(1,h):
    for j in range(1,w):
        dp[i][j]+=dp[i-1][j-1]*D[j-1][j]
    for j in range(w-1):
        dp[i][j]+=dp[i-1][j+1]*D[j+1][j]
    for j in range(w):
        dp[i][j]+=dp[i-1][j]*D[j][j]
        dp[i][j]%=mod
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

# ループを回す
for h in range(H):
    X, Y, Z = 0, 0, 0

    # 0: 線あり、1: 線なし
    for i in range(2 ** (W-1)):
        # 連続した1がある→隣接する列に線が引かれている
        if bin(i).count('11') >= 1:
            continue
        perm = [k for k 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):
            dp[h+1][perm[j]] += dp[h][j]
            dp[h+1][perm[j]] %= MOD


# 答えを得て出力
print(dp[H][K-1])
# print(dp)

Submission status: Accepted

Solution code:
h,w,k = (int(x) for x in input().split())
MOD = 1000000007

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

# 初期条件
fib[1] = 1
dp[0][1] = 1
# フィボナッチ
for i in range(2,w+1):
  fib[i] = fib[i-1] + fib[i-2]
  
for i in range(1, h+1):
  for j in range(1, w+1):
    dp[i][j] = (dp[i - 1][j - 1]*fib[j - 1]*fib[w - j + 1]+dp[i - 1][j]*fib[j]*fib[w - j + 1]+dp[i - 1][j + 1]*fib[j]*fib[w - j])%MOD
                                                                                                                          
print(dp[h][k])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

MOD = 1000000007  # type: int

def solve(h: int, w: int, k: int):
    wc = [1] * 9

    for i in range(2, 9):
        wc[i] = wc[i-1] + wc[i-2]

    dp = [0] * (w+2)
    dp[1] = 1
    for i in range(h):
        tmp = [0] * (w+2)
        for j in range(1, w+1):
            tmp[j] = dp[j] * wc[j-1] * wc[w-j]
            if j > 1:
                tmp[j] += dp[j-1] * wc[j-2] * wc[w-j]
            if j < w:
                tmp[j] += dp[j+1] * wc[j-1] * wc[w-j-1]
            tmp[j] = tmp[j] % MOD
        dp = tmp
    print(dp[k])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 = map(int,input().split())
move= [0]*(W-1)
count = 0
MOD = 10**9+7

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

for i in range(2**(W-1),2**W):
    b = bin(i)[3:]
    flag = True
    for j in range(W-2):
        if b[j] == '1' and b[j+1] == '1':
            flag = False
    if flag :
        count += 1
        for j in range(W-1):
            move[j] += int(b[j])

DP = [[0]*W for i in range(H+1)]
DP[0][0] = 1
for i in range(H):
    for j in range(W):
        if j == 0:
            DP[i+1][j] = (DP[i][j]*(count - move[0]) + DP[i][j+1]*move[0])%MOD
        elif j == W-1:
            DP[i+1][j] = (DP[i][j-1] * move[j-1] + DP[i][j]*(count - move[j-1])) % MOD
        else:
            DP[i+1][j] = (DP[i][j-1] * move[j-1] + DP[i][j]*(count - move[j] - move[j-1]) + DP[i][j+1]*move[j]) % MOD
print(DP[-1][K-1])

Submission status: Accepted

Solution code:
base = 10 ** 9 + 7
h, w, k = map(int, input().split())
wc = [1] * 9

for i in range(2, 9):
    wc[i] = wc[i-1] + wc[i-2]

dp = [0] * (w+2)
dp[1] = 1
for i in range(h):
    tmp = [0] * (w+2)
    for j in range(1, w+1):
        tmp[j] = dp[j] * wc[j-1] * wc[w-j]
        if j > 1:
            tmp[j] += dp[j-1] * wc[j-2] * wc[w-j]
        if j < w:
            tmp[j] += dp[j+1] *wc[j-1] * wc[w-j-1]
        tmp[j] = tmp[j] % base
    dp = tmp
print(dp[k])