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: Wrong Answer

Solution code:
def mod_cmb(n,k,mod):
    def ext_gcd(a,b):
        if b == 0:
            return a,1,0
        else:
            d,x,y=ext_gcd(b,a%b)
            x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1,n+1):
        p=(p*i)%mod
    for i in range(2,k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q,mod)[1]%mod)%mod)


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

mod=10**9+7

def c(a):
    return sum(mod_cmb(a,i,mod)for i in range(a//2)) #つなぐ本数
        
cmbnobasu=[]
for i in range(w): #何本目から右に伸ばすか
    l=i
    r=w-i-2
    cmbnobasu.append((c(l)+1)*(c(r)+1))
cmbnobasanai=[]
for i in range(w): #伸ばさない
    l=i
    r=w-i-1
    cmbnobasanai.append((c(l)+1)*(c(r)+1))
#print(cmbnobasu)
#print(cmbnobasanai)

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

for i in range(h):
    for j in range(w):
        if 0<j:
            dp[i+1][j-1]+=dp[i][j]*cmbnobasu[j-1]%mod #右に伸ばしたのは左に伸ばす+1と同義
        if j<w-1:
            dp[i+1][j+1]+=dp[i][j]*cmbnobasu[j]%mod
        dp[i+1][j]+=dp[i][j]*cmbnobasanai[j]%mod
#print(dp)
print(dp[-1][k-1]%mod)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7
if W == 1:
    print(1)
    exit()
ladder = W - 1
num_lad = [0] * ladder
limit = 0 #ハシゴの掛け方の総数
for i in range(2 ** ladder):
    flag = True
    for j in range(ladder-1):
        if (i >> j) & 1 and (i >> j+1) & 1:
            flag = False
    if not flag:
        continue
    limit += 1
    for j in range(ladder):
        # iのbitをj右にシフトしたらフラグが立っているかチェック
        if ((i >> j) & 1):
            num_lad[j] += 1

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

for i in range(1, H+1):
    for j in range(W):
        if j == 0:
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[0]) + dp[i-1][j+1] * num_lad[1]) % MOD
        elif j == (W-1):
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[0]) + dp[i-1][j-1] * num_lad[ladder-1]) % MOD
        else:
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[j-1] - num_lad[j]) + \
                    dp[i-1][j+1] * num_lad[j] + dp[i-1][j-1] * num_lad[j-1]) % MOD

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

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
k -= 1
mod = 1000000007
 
if w==1:
    print(1)
    exit()
 
dp = [[0 for _ in range(w)] for _ in range(h+1)]
dp[0][0] = 1
 
for hi in range(1,h+1):
    for b in range(2**(w-1)):
        judge = False
        for i in range(w-2):
            if (b>>i)&1 == 1:
                judge = True
                break
        if judge:
            continue
 
        perm = [i for i in range(w)]
        for i in range(w-1):
            if (b>>i)&1==1:
                perm[i],perm[i+1] = perm[i+1],perm[i]
        for i in range(w):
            dp[hi][perm[i]]  = (dp[hi][perm[i]]+dp[hi-1][i])%mod
 
print(dp[h][k])

Submission status: Wrong Answer

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

for k in range(H):
    for i in range(2**(W-1)):
        b = format(i, "0{}b".format(W-1))
        flag = 1
        for j in range(len(b)-1):
            if b[j+1] == "1" and b[j] == "1":
                flag = 0
                break
        if flag == 0:
            continue

        for j in range(len(b)):
            if flag == 0:
                flag = 1
                continue
            if b[j] == "1":
                dp[k+1][j+1] += dp[k][j]
                dp[k+1][j] += dp[k][j+1]
                dp[k+1][j+1] %= mod
                dp[k+1][j] %= mod
                flag = 0
            else:
                dp[k+1][j] += dp[k][j]
                dp[k+1][j] %= mod
print(dp[H][K-1])

Submission status: Wrong Answer

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):
            dp2[wi] = dp1[wi - 1] * stick[wi - 1][1] + dp1[wi + 1] * stick[w - wi][1] + dp1[wi] * stick[wi - 1][0] * stick[w - wi][0]
            dp2[wi] %= mod
        dp1 = dp2
    print(dp2[k])

    return

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

Submission status: Wrong Answer

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('Ans=',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('Ans=',dp[-1][K-1]%(1000000007))

Submission status: Wrong Answer

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))
        for l in range(W-1):
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
          else:
            dp[i+1][l] += dp[i][l]
        #print(dp[i+1])

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

Submission status: Wrong Answer

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

if w == 1:
    print(1)
else:
    acr_list = []
    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_list.append(exist)

    #print(acr_list)

    acr_sum = [[0,0] for i in range(w-1)]
    for j in range(len(acr_list)):
        for i in range(w-1):
            acr_sum[i][0] += 1 - acr_list[j][i]
            acr_sum[i][1] += acr_list[j][i]
            #print(acr_sum)
    #print(acr_sum)

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

    for t in range(h):
        nex[0] = (cur[0] * acr_sum[0][0] + cur[1] * acr_sum[0][1]) % MOD
        for m in range(1,w-1):
            nex[m] = (cur[m-1] * acr_sum[m-1][1] + cur[m+1] * acr_sum[m][1] + cur[m] * (len(acr_list)-acr_sum[m-1][1]-acr_sum[m][0])) % MOD
        nex[w-1] = (cur[w-1] * acr_sum[w-2][0] + cur[w-2] * acr_sum[w-2][1]) % MOD
        cur = nex[:]
        #print(cur)

    print(cur[k-1])

Submission status: Wrong Answer

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[0]) % MOD
print(DP[-1][K-1])

Submission status: Wrong Answer

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])

print(move,count)

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[0]) % MOD
print(DP[-1][K-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

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

mod = int(1e9+7)

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

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

draw_line = [0 for _ in range(W)]
draw_line[0] = 1
if W > 1:
    draw_line[1] = 1
for i in range(2, W):
    draw_line[i] = draw_line[i-1] + draw_line[i-1]

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1, H+1):
    for w in range(W):
        # from left
        if w > 0:
            dp[h][w] += dp[h-1][w-1] * draw_line[w-1] * draw_line[W-w-1]
        # from up
        dp[h][w] += dp[h-1][w] * draw_line[w] * draw_line[W-w-1]
        # from right
        if w < W-1:
            dp[h][w] += dp[h-1][w+1] * draw_line[w] * draw_line[W-w-2]

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

Submission status: Wrong Answer

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

# nonsence_line_pattern[l][s]
# l: line length
# s: 1 if end with draw line
nonsence_line_pattern = [[1 for _ in range(2)] for _ in range(W)]
for i in range(2, W):
    nonsence_line_pattern[i][0] = nonsence_line_pattern[i-1][0] + nonsence_line_pattern[i-1][1]
    nonsence_line_pattern[i][1] = nonsence_line_pattern[i-1][0]

# focus on line between i to i+1
different_line_pattern = [nonsence_line_pattern[i][0] * nonsence_line_pattern[W-i-2][0] for i in range(W-1)]

# no translation
same_line_pattern = [0 for i in range(W)]
same_line_pattern[0] = nonsence_line_pattern[W-1][0] if W > 1 else 1
same_line_pattern[W-1] = nonsence_line_pattern[W-1][0] if W > 1 else 1
for i in range(1, W-1):
    same_line_pattern[i] = nonsence_line_pattern[i][0] * nonsence_line_pattern[W-i][0]

dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1, H+1):
    for w in range(W):
        # from up
        dp[h][w] += dp[h-1][w] * same_line_pattern[w]
        # from right
        if w < W-1:
            dp[h][w] += dp[h-1][w+1] * different_line_pattern[w]
        # from left
        if w > 0:
            dp[h][w] += dp[h-1][w-1] * different_line_pattern[w-1]

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

Submission status: Wrong Answer

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

memo = [-1]*(W+1)
memo[0] = 1
memo[1] = 1
def cnt(n):
	if memo[n] >= 0:
		return memo[n]
	memo[n] = cnt(n-1) + cnt(n-2)
	return memo[n]

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

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

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

print(dp[H][K])

Submission status: Wrong Answer

Solution code:
import itertools

height, width, k = map(int, input().split())
k -= 1

MOD = 1000000007

# 1 つの行について valid な線の引き方を列挙
patterns = []
for r in range(width - 1):
    for pattern in itertools.combinations(range(width - 1), r):
        # 隣り合ってたらだめ
        if all(abs(a - b) != 1 for a, b in zip(pattern[:-1], pattern[1:])):
            patterns.append(pattern)

# counts[w][v]: 1 行で w から v へ行けるパターンの数
counts = [[0 for _ in range(width)] for _ in range(width)]
for pattern in patterns:
    for w in range(width):
        if w in pattern:
            counts[w][w + 1] += 1
        elif w - 1 in pattern:
            counts[w][w - 1] += 1
        else:
            counts[w][w] += 1

# 0 から高さ h の w に行けるパターン数
# dp[h][w]
dp = [[0 for _ in range(width)] for _ in range(height)]
dp[0] = counts[0].copy()
for h in range(height - 1):
    for w in range(width):
        # w に来れるパターン数
        dp[h + 1][w] = sum([dp[h][v] * counts[v][w] for v in range(width)]) % MOD

print(dp[-1][k])

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
# (上から, 左右から)の通り数
memo = [[0]*w for i in range(h+1)]
for i in range(0, w):
    memo[0][i] = 0
memo[0][0] = 1

# print(memo)

for i in range(1, h+1):
    for j in range(0, 1 << (w-1)):
        skip = False
        for l in range(w-1):
            skip = skip or ((j >> l) & 1 and (j >> (l+1)) & 1)
        #print(skip)
        if not skip:
            for l in range(w):
                memo[i][l] += memo[i-1][l] if (l-1 >= 0 and not (j >> (l-1)) & 1) or (l+1 < w and not (j >> l) & 1) or w == 1 else 0
                memo[i][l] += memo[i-1][l-1] if l-1 >= 0 and (j >> (l-1)) & 1 else 0
                memo[i][l] += memo[i-1][l+1] if l+1 < w and (j >> l) & 1 else 0
                memo[i][l] = memo[i][l] % 1000000007

# print(memo)
print(memo[h][k-1])

Submission status: Wrong Answer

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

r = 10**9 + 7

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

dp[0][0]=1

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

if W!=1:
    for i in range(H):
        for j in range(W):
            if j==0:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j+1])%r
            elif j==W-1:
                dp[i+1][j]=(num[W-1]*dp[i][j]+num[W-2]*dp[i][j-1])%r
            else:
                dp[i+1][j]=(num[j]*num[W-j-1]*dp[i][j]+num[j-1]*num[W-j-1]*dp[i][j-1]+num[j]*num[W-j-2]*dp[i][j+1])%r

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

Submission status: Wrong Answer

Solution code:
def num_amida(cur_h,h,w,k,dp):
    start_list = [d for d in dp]
    if cur_h>h:
        return dp
    else:
        if cur_h==1:
            start=0
            for end in range(w):
                if start==end:
                    dp[end]+=w-2 + 1
                    #dp[end]=dp[end]*(w-2 + 1)
                elif end==start-1 or end==start+1:
                    dp[end]+=w-2-1 + 1
                    #dp[end]=dp[end]*(w-2-1 + 1)
        else:
            dp=[0 for _ in range(w)]
            for start in range(w):
                if start_list[start] == 0:
                    continue
                else:
                    for end in range(w):
                        #print("---"+str(cur_h)+"---")
                        #print(start_list)
                        #print(dp)
                        if start==end:
                            dp[end]+=start_list[start]*(w-2 + 1)
                        elif end==start-1 or end==start+1:
                            dp[end]+=start_list[start]*(w-2-1 + 1)
        cur_h+=1
        dp = num_amida(cur_h,h,w,k,dp)
        return dp
    
import numpy as np
h,w,k = map(int, input().split())
#h,w,k=2,3,1
dp=[0 for _ in range(w)]
dp = num_amida(1,h,w,k,dp)
#print(dp)
print(dp[k-1]%1000000007)

Submission status: Wrong Answer

Solution code:
def num_amida(cur_h,h,w,k,dp):
    start_list = [d for d in dp]
    if cur_h>h:
        return dp
    else:
        if cur_h==1:
            start=0
            for end in range(w):
                if start==end:
                    dp[end]+=w-2 + 1
                    #dp[end]=dp[end]*(w-2 + 1)
                elif end==start-1 or end==start+1:
                    dp[end]+=w-2-1 + 1
                    #dp[end]=dp[end]*(w-2-1 + 1)
        else:
            for start in range(w):
                if start_list[start] == 0:
                    continue
                else:
                    for end in range(w):
                        #print("---"+str(cur_h)+"---")
                        #print(start_list)
                        #print(dp)
                        if start==end:
                            dp[end]=start_list[start]*(w-2 + 1)
                            #if dp[end]==0:
                             #   dp[end]+=w-2 + 1
                            #else:
                             #   dp[end]+=start_list[start]*(w-2 + 1)
                        elif end==start-1 or end==start+1:
                            dp[end]=start_list[start]*(w-2-1 + 1)
                            #if dp[end]==0:
                             #   dp[end]+=w-2-1 + 1
                            #else:
                             #   dp[end]+=start_list[start]*(w-2-1 + 1)
        cur_h+=1
        dp = num_amida(cur_h,h,w,k,dp)
        return dp
    
import numpy as np
h,w,k = map(int, input().split())
#h,w,k=2,3,3
dp=[0 for _ in range(w)]
dp = num_amida(1,h,w,k,dp)
#print(dp)
print(dp[k-1]%1000000007)

Submission status: Wrong Answer

Solution code:
def valid(x):
    odd_mask = 85    # 01010101
    even_mask = 170  # 10101010
    return (x & odd_mask) >> 1 & (x & even_mask) == 0 and (x & odd_mask) << 1 & (x & even_mask) == 0

def yoko(x):
    a, b, c = 0, 0, 0
    for bit in range(1<<W-1):
        if not valid(bit):
            continue
        if W - x - 1 >= 0 and bit >> (W - x - 1) & 1:
            a += 1
        elif W - x - 2 >= 0 and bit >> (W - x - 2) & 1:
            c += 1
        else:
            b += 1
    return a, b, c

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

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

for i in range(H):
    for j in range(W):
        if j <= W-2:
            a, b, c = yoko(j)
        elif j == W-1:
            a, b, c = 0, 1, 0
        if j - 1 >= 0:
            dp[i+1][j-1] += a * dp[i][j]
            dp[i+1][j-1] %= BIG
        dp[i+1][j] += b * dp[i][j]
        dp[i+1][j] %= BIG
        if j + 1 < W:
            dp[i+1][j+1] += c * dp[i][j]
            dp[i+1][j+1] %= BIG
print(dp[H][K-1])

Submission status: Wrong Answer

Solution code:


H,W,K = [int(n) for n in input().split()]
memo = [[0 for _ in range(W)] for __ in range(H+1)]
memo[0][0] = 1
MOD = 10**9 + 7
for h in range(1,H+1):
    for pt in range((1 << W-1)):#1 == 線あり 0 == 線なし　とする
        # pts = bin(pt)[2:]
        # pts = pts[::-1]#反転
        if "11" in bin(pt): continue
        #各パターンの時の各線の計算
        goto = [i for i in range(W)]
        for i in range(W):
            if (1 << i) & pt:
                goto[i], goto[i + 1] = goto[i + 1], goto[i]
        for i in range(W):
            memo[h][goto[i]] += memo[h-1][i]
            memo[h][goto[i]] %= MOD
        # print(goto if h == 1 else "")
for ht in range(H+1):
    print(memo[ht])

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

Submission status: Wrong Answer

Solution code:
from sys import exit
H,W,K = [int(n) for n in input().split()]
memo = [[0 for _ in range(H+1)] for __ in range(W)]
memo[0][0] = 1
for h in range(1,H+1):
    for pt in range((1 << W-1)):#1 == 線あり 0 == 線なし　とする
        pts = bin(pt)[2:]
        pts = pts[::-1]#反転
        if "11" in pts: continue
        # print(pts)
        #各パターンの時の各線の計算
        for i in range(W):
            if i < len(pts) and pts[i] == "1":
                # print(i)
                memo[i][h] += memo[i+1][h-1]
                memo[i+1][h] += memo[i][h-1]
                i+=1#よみとばす
            else:
                memo[i][h] += memo[i][h-1]
print(memo[K-1][H])
exit()

Submission status: Wrong Answer

Solution code:
H,W,K = tuple(map(int,input().split()))
m = 1000000007
def get (bou_no_kazu):
    ##print("get",bou_no_kazu)
    return 2**(bou_no_kazu-1) / 2

def n(nodes,from_idx,to_idx):
    ret = nodes[from_idx]
    ## print("r",ret)
    if min(from_idx,to_idx) > 1:
        #print("left")
        ret *= get(min(from_idx,to_idx))+1
    if max(from_idx,to_idx) < W-2:
        #print("right")
        ret *= get(W-max(from_idx,to_idx)-1)+1
    return ret
    
prev_node = [1]*1+[0]*(W-1)
next_node = [1]*W
for i in range(H):
    for j in range(W):
        #print(prev_node,next_node)
        next_node[j] = n(prev_node,j,j)
        if j-1 >= 0:
            next_node[j] += n(prev_node,j-1,j)
        if j+1 <= W-1:
            next_node[j] += n(prev_node,j+1,j)
    
    prev_node = [i%m for i in next_node.copy()]
print(int(next_node[K-1]))

Submission status: Wrong Answer

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

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

    

for i in range(1,H+1):
    Alloc = [0]*9    
    for x in range(max((2**(W-1)-1),1)):
        tmp = x
        for y in range(1,8):  
            Alloc[y] = tmp%2
            tmp /= 2  
        for y in range(0,9):
            if Alloc[y] == 1 and Alloc[y+1] == 1:
                break
        else:
            for j in range(1,W+1):
                if Alloc[j-1] == 1:
                    dp[i][j] += dp[i-1][j-1]
                if Alloc[j] == 1:
                    dp[i][j] += dp[i-1][j+1]
                else:
                    dp[i][j] += dp[i-1][j]
                dp[i][j] %= 1000000007
                    
print(dp[H][K])

Submission status: Wrong Answer

Solution code:
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper

@memorize
def amida(W):   # W本の棒に対する1行アミダの引き方
    if W<2:
        return 1
    else:
        return amida(W-1)+amida(W-2)

@memorize
def amida2(H, W, x, y=1):
    if H==0:
        return 1 if x==y else 0
    a = 0 if x==1 else amida(x-2)*amida(W-x)*amida2(W, H-1, x-1, y)
    b = amida(x-1)*amida(W-x)*amida2(W, H-1, x, y)
    c = 0 if x==W else amida(x-1)*amida(W-x-1)*amida2(W, H-1, x+1, y)
    return (a+b+c)%1000000007
print(amida2(*map(int, input().split())))

Submission status: Wrong Answer

Solution code:
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper

@memorize
def amida(W):   # W本の棒に対する1行アミダの引き方
    if W<2:
        return 1
    else:
        return amida(W-1)+amida(W-2)

@memorize
def amida2(W, H, x, y=1):
    if H==0:
        return 1 if x==y else 0
    a = 0 if x==1 else amida(x-2)*amida(W-x)*amida2(W, H-1, x-1, y)
    b = amida(x-1)*amida(W-x)*amida2(W, H-1, x, y)
    c = 0 if x==W else amida(x-1)*amida(W-x-1)*amida2(W, H-1, x+1, y)
    return (a+b+c)%1000000007

Submission status: Wrong Answer

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

onerow_t = [0]*(w-1) # i番目の横棒があるような1行の線の引き方の場合の数

for i in range(1<<(w-1)):
    tf = [None]*(w-1)
    valid = True
    for d in range(w-1):
        if (i>>d)&1 != 0:
            tf[d] = True
        if d>0 and tf[d-1] and tf[d]:
            valid = False
            break
    # print(bin(i), tf, valid)
    if valid:
        for d in range(w-1):
            if tf[d]:
                onerow_t[d] += 1

onerow_sum = sum(onerow_t)+1

for i in range(1,h+1):
    for j in range(w):
        tmp = onerow_sum
        if 0<=j-1:
            dp[i][j] += onerow_t[j-1]*dp[i-1][j-1]
            tmp -= onerow_t[j-1]
        if j+1<w:
            dp[i][j] += onerow_t[j]*dp[i-1][j+1]
            tmp -= onerow_t[j]
        # print('i,j,tmp',i,j,tmp)
        dp[i][j] += tmp*dp[i-1][j]
        dp[i][j] = dp[i][j]%mod

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

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
law = 1000000007
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] += dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)] % law
            if col < w - 1:
                dp[row][col] += dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)] % law
            dp[row][col] += dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)] % law
print(dp[h][k-1])

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] += dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]
            if col < w - 1:
                dp[row][col] += dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]
            dp[row][col] += dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]
print(dp[h][k-1])

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
dp = [[0 for _ in range(w)] for _ in range(h+1)]
perm = [1, 2, 3, 5, 8, 13, 21, 34]
for row in range(h+1):
    for col in range(w):
        if row == 0:
            dp[row][col] = int(col == 0)
        else:
            if col > 0:
                dp[row][col] += dp[row-1][col-1] * perm[max(0,col-2)] * perm[max(0, w-col-2)]
            if col < w - 1:
                dp[row][col] += dp[row-1][col+1] * perm[max(0,col-1)] * perm[max(0, w-col-3)]
            dp[row][col] += dp[row-1][col] * perm[max(0,col-1)] * perm[max(0,w-col-2)]
print(dp)