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:

import sys
import itertools

#h,w,k=map(int,input().split())
h,w,k=7,1,1
h,w,k=2,3,3
h,w,k=2,3,1
h,w,k=3,5,1
h,w,k=15,8,5

if w==1:
    print(1)
    sys.exit()
    
mod=10**9+7

ww=[]
for i in itertools.product([0,1], repeat=w-1):
    yn=""
    for wi in range(w-2):
        if i[wi]==1 and i[wi+1]==1:
            yn="no"
            break
    if yn=="" :
        ww.append(i)

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

for i in range(h):
    for wi in ww:
        j=0
        if wi[j]==1:
            dp[i+1][j]=(dp[i+1][j]+dp[i][j+1])%mod
        else:    
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod

        for j in range(1,w-1):
            if wi[j-1]==1:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j-1])%mod
            elif wi[j]==1:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j+1])%mod
            else:    
                dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        j=w-1
        if wi[j-1]==1:
            dp[i+1][j]=(dp[i+1][j]+dp[i][j-1])%mod
        else:    
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
                
print(dp[h][k-1])

Submission status: Wrong Answer

Solution code:
import sys

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

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

fn = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

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

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

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
dp = [[0]*(W+1) for _ in range(H+1)]
dp[0][1] = 1
mod = 10**9+7
for i in range(1, H+1):
    for j in range(1, W+1):
        t_1 = (j - 1)//2 + (W - j)//2
        t_2 = (j - 1)//2 + (W - j - 1)//2
        t_3 = (j - 2)//2 + (W - j)//2
        dp[i][j] += dp[i-1][j]*pow(2, t_1, mod)
        if j+1 <= W:
            dp[i][j] += dp[i-1][j+1]*pow(2, t_2, mod)
        if j-1 >= 1:
            dp[i][j] += dp[i-1][j-1]*pow(2, t_3, mod)
        dp[i][j] %= mod

print(dp[H][K])

Submission status: Wrong Answer

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

import itertools
mod = 1000000007

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

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

dp[0][0] = 1

for h_ in range(1, h+1):
    for bridges in itertools.product([0, 1], repeat=w-1):
        flag = 0
        for j in range(len(bridges)-1):
            if bridges[j] == 1 and bridges[j+1] == 1:
                flag = 1
        if flag == 1:
            continue
        # print(bridges)

        for w_ in range(w):
            if w_ > 0:
                if bridges[w_-1] == 1:
                    dp[h_][w_] += dp[h_-1][w_-1] % mod
                    continue
            elif w_ < w-1:
                if bridges[w_] == 1:
                    dp[h_][w_] += dp[h_-1][w_+1] % mod
                    continue
            dp[h_][w_] += dp[h_-1][w_] % mod

# print(dp)
print(dp[-1][k-1] % mod)

Submission status: Wrong Answer

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,k=MI()
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+1<w:
            left=j//2
            right=(w-j-2)//2
            dp[i+1][j+1]+=(dp[i][j]*(2**(left+right)))
        if 0<=j<w:
            left=j//2
            right=(w-j-1)//2
            dp[i+1][j]+=(dp[i][j]*(2**(left+right)))
        if 0<=j-1<w:
            left=(j-1)//2
            right=(w-j-1)//2
            dp[i+1][j-1]+=(dp[i][j]*(2**(left+right)))
#print(dp)
print(dp[-1][k-1]%mod)

Submission status: Wrong Answer

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

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for bit in range(1<<(W-1)):
        if "11" in bin(bit): continue
        for w in range(W):
            if w > 0 and (bit>>(w-1))&1:
                dp[h+1][w-1] += dp[h][w]
                dp[h+1][w-1] %= MOD
            if (bit>>w)&1:
                dp[h+1][w+1] += dp[h][w]
                dp[h+1][w+1] %= MOD
            if (bit>>w)&1 == 0:
                dp[h+1][w] += dp[h][w]
                dp[h+1][w] %= MOD

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

Submission status: Wrong Answer

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

dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for bit in range(1<<(W-1)):
        if "11" in bin(bit): continue
        for w in range(W):
            if (bit>>w)&1 == 0:
                dp[h+1][w] += dp[h][w]
                dp[h+1][w] %= MOD
            else:
                dp[h+1][w+1] += dp[h][w]
                dp[h+1][w+1] %= MOD
            if w > 0 and (bit>>(w-1))&1:
                dp[h+1][w-1] += dp[h][w]
                dp[h+1][w-1] %= MOD

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

Submission status: Wrong Answer

Solution code:
# |-| | | | |
# のように一番左の一本が決まったとき、残りの
#     | | | |
# には、線を引く場所が3つある
# 線を引く場所がN個あるときの線の引き方の組み合わせは
# A[1] = 2, A[2] = 3, A[N] = A[N - 2] + A[N - 1]
# のほぼフィボナッチ数列
# 2,3,5,8,13...
# これをあらかじめ最大数ぶん求めておく
# 横棒W本に対して、W - 1個の間隔があり、そのうち端の2か所が埋まった状態が最大なのでW - 3
# これを求める

import sys
readline = sys.stdin.readline

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

P = [0] * max(W - 2 + 1,3)
P[1],P[2] = 2,3
for i in range(3, len(P)):
  P[i] = P[i - 1] + P[i - 2]
  
# [0, 2, 3, 5, 8, 13, 21, 34, ...]

# 通らない線は上記で算出できるので、通る線を考える
# 上からi段目まで終えた時点で、縦棒jにいるときの場合の数でDPする

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

dp[0][0] = 1 # 上から0段目を終えた時点(まだ何もしていない)ときに0にいるので1通り

def calc(L,R): # LとRの間に線を引いた場合の、残りの線の引き方
#  print("calc L",L,"R",R)
  res = 1
  if 1 < L:
    # | | |-| Lが2のときはじめてスペースが1 (L - 1)できる
    res *= P[L - 1]
#    print("P[L - 2]",P[L - 2],"res",res)
    res %= DIV
  if (W - 1) - (R + 1) >= 1:
    # |-| | | R + 2 = W - 1のときはじめてスペースが1(W - R)できる
#    print(min((W - 1) - (R + 1),len(P)))
    res *= P[(W - 1) - (R + 1)]
#    print("P[(W - 1) - (R + 1)]",min((W - 1) - (R + 1),len(P)),"res",res)
    res %= DIV
#  print(res,"通り")
  return res
  
# 右に移動する、左に移動する、何もしない、の3通りでDP
for i in range(H):
  for j in range(W):
    # 右に移動する
    if j + 1 < W:
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
      dp[i + 1][j + 1] += dp[i][j] * calc(j, j + 1)
      dp[i + 1][j + 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j + 1",j + 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j + 1]",dp[i + 1][j + 1])
    # 左に移動する
    if j - 1 >= 0:
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
      dp[i + 1][j - 1] += dp[i][j] * calc(j - 1,j)
      dp[i + 1][j - 1] %= DIV
#      print("i",i,"j",j,"からi + 1",i + 1,"j - 1",j - 1,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j - 1]",dp[i + 1][j - 1])
    # 何もしない
#    print("i",i,"j",j,"からi",i,"j",j,"に移動する dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
    dp[i + 1][j] += dp[i][j] * calc(j,j) # 左端も右端も同じ
    dp[i + 1][j] % DIV
#    print("i",i,"j",j,"からi",i,"j",j,"に移動した dp[i][j]",dp[i][j],"dp[i + 1][j]",dp[i + 1][j])
#  for d in dp:
#    print(dp)

    
# i = H段目まで終えた時点で、j = K - 1にいる場合の数
print(dp[H][K - 1])

Submission status: Wrong Answer

Solution code:
h,w,K = map(int,input().split())

mod = 10**9+7

num = 2**(w-1)

li = []

if w == 1:
    if K == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(num):
    tmp = format(i, '0'+str(w-1)+'b')
    cnt = 0
    for j in range(w-1):
        if tmp[j] == '1':
            if cnt == 1:
                break
            else:
                cnt = 1
        else:
            cnt = 0
        if j == w-2:
            li.append(tmp)
    #print(tmp)

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

dp[0][0] = 1

print(li)
exit()

for i in range(h):
    #print(i)
    for j in range(len(li)):
        for k in range(w):
            #print(li[j],li[j][0] == '1')
            if k == 0:
                if li[j][k] == '1':
                    dp[i+1][k+1] += dp[i][k]
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            elif k == w-1:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
            else:
                if li[j][k-1] == '1':
                    dp[i+1][k-1] += dp[i][k]
                    dp[i+1][k-1] %= mod
                elif li[j][k] == '1':
                    #print(dp[i][k],i,k,i+1,k+1)
                    dp[i+1][k+1] += dp[i][k]
                    #print(dp[i+1][k+1],dp)
                    dp[i+1][k+1] %= mod
                else:
                    dp[i+1][k] += dp[i][k]
                    dp[i+1][k] %= mod
                    
print(dp)
print(dp[h][K-1])

Submission status: Wrong Answer

Solution code:
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 calc_pow(from_col, to_col):
  assert(1<=from_col<=w and 1<=to_col<=w)
  if from_col == 1 or to_col == 1 or from_col == w or to_col == w:
    return pow(2, max(w-1-2, 0), mod)
  else:
    return pow(2, max(w-1-3, 0), mod)


for t in range(1, h + 1):
  for i in range(1, w + 1):
    pattern_1 = dp[t-1][i-1] * calc_pow(i-1, i) if i > 1 else 0
    pattern_2 = dp[t-1][i+1] * calc_pow(i+1, i) if i < w else 0
    pattern_3 = dp[t-1][i] * (pow(2, max(w-1-2, 0), mod) if 1 < i < w else pow(2, max(w-1-1, 0), mod))
    dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

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

Submission status: Wrong Answer

Solution code:
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 calc_pow(from_col, to_col):
  assert(1<=from_col<=w and 1<=to_col<=w)
  if from_col == 1 or to_col == 1 or from_col == w or to_col == w:
    return pow(2, max(w-1-2, 0), mod)
  else:
    return pow(2, max(w-1-3, 0), mod)


for t in range(1, h + 1):
  for i in range(1, w + 1):
    pattern_1 = dp[t-1][i-1] * calc_pow(i-1, i) if i > 1 else 0
    pattern_2 = dp[t-1][i+1] * calc_pow(i+1, i) if i < w else 0
    pattern_3 = dp[t-1][i] * (pow(2, max(w-1-2, 0), mod) if 1 < i < w else pow(2, max(w-1-1, 0), mod))
    dp[t][i] = (pattern_1 + pattern_2 + pattern_3) % mod

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

Submission status: Wrong Answer

Solution code:

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

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

for x in range(w):
    dp[0][x]=1

for i in range(1,h+1):
    x=0
    while x<w:
        for mv in [-1,0,1]:
            if 0<= x+mv < w:
                dp[i][x]+=dp[i-1][x+mv]
        x+=1
print(dp[h][k-1])

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

H,W,K = LI()

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

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

good = []
for ami in range(2**(W-1)-1):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

H,W,K = LI()

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

good = []
for ami in range(2**(W-1)-1):
    b = 1
    m = -2
    for i in range(W-1):
        if b & ami:
            if i <= m + 1:
                break
            m = i
        b <<= 1
    else:
        s = []
        b = 1
        for i in range(W):
            s.append(ami & b > 0)
            b <<= 1
        good.append([0] + s + [0])

for i in range(H):
    for ami in good:
        for j in range(W):
            if ami[j] == 0 and ami[j+1] == 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            elif ami[j] == 1:
                dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD

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

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc113/tasks/abc113_d
# 1からスタートKまで到着
# 横棒はH本引ける
# 縦棒はW本ある

# DP的に数え上げることを考える
# DP[i][j]...(0,i]まで考慮したときに、jにたどり着ける通りの数
MOD = 10**9 + 7
ra = range
enu = enumerate
H, W, K = map(int, input().split())


'''
DP[i][j]...(0,i]まで考慮したときに、jにたどり着ける通りの数

更新則
if iにおいてjとj+1の間に横棒があったら
DP[i+1][j+1] += D[i][j]
DP[i+1][j] += D[i][j+1]
else
DP[i+1][j] = D[i][j]

for all paterns at i

初期条件
DP[i][j]=0
DP[0][0]=1
'''

if W == 1:  # コーナーケース処理
    print(1)
    exit()


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


def ret_valid_swapset():
    # (j,j+1)でswapできるならjで1に成るようにする
    for p in iter_p_adic(2, W - 1):
        pre = 0
        skip = False
        for pp in p:
            if pre == 1 and pp == 1:
                skip = True
                break  # 条件を満たさない
            pre = pp
        if skip:
            continue
        yield p


pattern = list(ret_valid_swapset())

DP = [[0] * W for _ in ra(H + 1)]
DP[0][0] = 1
for i in ra(H):
    for p in pattern:
        for j, is_swap in enu(p):
            if is_swap:
                DP[i + 1][j + 1] += DP[i][j]
                DP[i + 1][j] += DP[i][j + 1]
            else:
                DP[i + 1][j] += DP[i][j]
    # あまりの処理
    for j in ra(W):
        DP[i + 1][j] %= MOD
print(DP[H][K - 1])
# from pprint import pprint
# print(*DP, sep='\n')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    h,w,k = map(int, input().split())
    dp = [[0]*w for _ in range(h+1)]
    dp[0][0] = 1

    pattern = []
    if w > 2:
        for i in range(1<<(w-1)):
            for j in range(w-2):
                if (i>>j) & 1 and (i>>(j+1)) & 1:
                    continue
                pattern.append(i)
    else:
        print(1)
        exit()
    
    for i in range(h):
        for j in range(w):
            for p in pattern:
                if j == 0:
                    if p & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                elif j == w-1:
                    if (p>>(w-2)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
                else:
                    if (p>>(j-1)) & 1:
                        dp[i+1][j-1] += dp[i][j] % mod
                    elif (p>>j) & 1:
                        dp[i+1][j+1] += dp[i][j] % mod
                    else:
                        dp[i+1][j] += dp[i][j] % mod
    print(dp[-1][k-1] % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

b=[]
for i in range(2**(w-1)):
  b.append(format(i,'0'+str(w-1)+'b'))
l=[]
for i in range(len(b)):
  ct=0
  for j in range(w-2):
    if b[i][j]!='1' or b[i][j+1]!='1':
      ct+=1
  if ct==w-2:
    l.append(b[i])

count=[[0,0,0] for i in range(w)]
for i in range(len(l)):
  if l[i][0]=='0':
    count[0][1]+=1
  if l[i][0]=='1':
    count[0][2]+=1
  if l[i][-1]=='1':
    count[-1][0]+=1
  if l[i][-1]=='0':
    count[-1][1]+=1
  for j in range(w-2):
    if l[i][j:j+2]=='10':
      count[j+1][0]+=1
    if l[i][j:j+2]=='00':
      count[j+1][1]+=1
    if l[i][j:j+2]=='01':
      count[j+1][2]+=1

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

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import itertools


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

DP = [0] * w
DP[0] = 1
mod = 10**9 + 7

patterns = []

for line_count in range(w):
    candidates = itertools.combinations(range(w-1), line_count)

    for pattern in candidates:
        usable = True
        prev = 10

        for num in pattern:
            if num == prev + 1:
                usable = False
                break
            else:
                prev = num

        if usable:
            patterns.append(pattern)

for i in range(h):
    next_DP = [0] * w

    for pattern in patterns:
        straight = set(range(w))
        for line in pattern:
            next_DP[line] += DP[line+1]
            next_DP[line] %= mod
            next_DP[line+1] += DP[line]
            next_DP[line+1] % mod
            straight.discard(line)
            straight.discard(line+1)

        for line in straight:
            next_DP[line] += DP[line]
            next_DP[line] %= mod

    DP = next_DP

ans = DP[k-1]
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

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

for _ in range(H):

    T = [0] * W

    for i in range(W):
        if 0 < i:
            T[i] += T[i - 1] * fib[i - 1] * fib[W - i - 1]

        T[i] += T[i] * fib[i] * fib[W - i - 1]

        if i < W - 1:
            T[i] += dp[i + 1] * fib[i] * fib[W - i - 2]

        T[i] %= mod

    dp = T

print(dp[K - 1])

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

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

DP = [[1]+[0]*(W-1), [0]*W]
for i in range(H):
    for j in range(1<<(W-1)):
        # あみだくじの正当性の判断
        flg = 0
        if W > 2:
            for k in range(1,W-1):
                if j&(1<<k) > 0 and j&(1<<(k-1)) > 0:
                    flg = 1
                    break
        if flg:
            break

        #DPの更新
        for k in range(W):
            if k < W-1:
                if j&(1<<k) > 0:
                    DP[1][k] += DP[0][k+1]
                else:
                    DP[1][k] += DP[0][k]
                DP[1][k] %= MOD
            if k > 0:
                if j&(1<<(k-1)) > 0:
                    DP[1][k] += DP[0][k-1]
                else:
                    DP[1][k] += DP[0][k]
                DP[1][k] %= MOD

        DP[0] = DP[1][:]
        DP[1] = [0]*W


print(DP[0][K-1])

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
ws=[0]*10
ws[0]=1
ws[1]=1
for i in range(2,10):
    ws[i]=ws[i-1]+ws[i-2]
dp=[[0 for i in range(h+1)] for j in range(w)]
dp[0][0]=1
mod=10**9+7
if w==1:
    print(1)
    exit()
for i in range(h):
    for j in range(w):
        if j==0:
            dp[0][i+1]=dp[0][i]*ws[w-1]+dp[1][i]*ws[max(0,w-2)]
            dp[0][i+1]%=mod
        elif j==w-1:
            dp[w-1][i+1]=dp[w-1][i]*ws[w-1]+dp[w-2][i]*ws[max(0,w-2)]
            dp[w-1][i+1]%=mod
        else:
            dp[j][i+1]=dp[j][i]*ws[max(0,j)]*ws[max(0,w-j-1)]+dp[j-1][i]*ws[max(0,j-2)]*ws[max(0,w-j-1)]+dp[j+1][i]*ws[max(0,j-1)]*ws[max(0,w-j-2)]
            dp[j][i+1]%=mod
print(dp[k-1][h]%mod)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
ws=[0]*10
ws[0]=1
ws[1]=1
for i in range(2,10):
    ws[i]=ws[i-1]+ws[i-2]
dp=[[0 for i in range(h+1)] for j in range(w)]
dp[0][0]=1
mod=10**9+7
if w==1:
    print(1)
    exit()
for i in range(h):
    for j in range(w):
        if j==0:
            dp[0][i+1]=dp[0][i]*ws[w-1]+dp[1][i]*ws[max(0,w-2)]
            dp[0][i+1]%=mod
        elif j==w-1:
            dp[w-1][i+1]=dp[w-1][i]*ws[w-1]+dp[w-2][i]*ws[max(0,w-2)]
            dp[w-1][i+1]%=mod
        else:
            dp[j][i+1]=dp[j][i]*ws[max(0,j)]*ws[max(0,w-j-1)]+dp[j-1][i]*ws[max(0,j-2)]*ws[max(0,w-j-1)]+dp[j+1][i]*ws[max(0,j-1)]*ws[max(0,w-j-2)]
            dp[j][i+1]%=mod
print(dp[k-1][h])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
h,w,k=map(int,input().split())
n=2**(w-1)
haji=[0,0]
tyuo=[0,0,0]
if w==1:
    print(1)
    exit()
# for i in range(n):
#     flag=0
#     for j in range(w-1):
#         bit=1<<j
#         if i & bit and i & (bit<<1):
#             flag=1
        
#     if flag==0:
        # print(i)
        # if i & 1:
        #     haji[0]+=1
        # else:
        #     haji[1]+=1
        # if w>2:
        #     if i & 1:
        #         tyuo[2]+=1
        #     elif i & 2:
        #         tyuo[0]+=1
        #     else:
        #         tyuo[1]+=1
haji.reverse()
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1

# print(tyuo)
# print(haji)
for l in range(h):
    for i in range(n):
        flag=0
        for j in range(w-1):
            bit=1<<j
            if i & bit and i & (bit<<1):
                flag=1
        
        if flag==0:
            flag2=0
            for j in range(w-1):
                bit=1<<j
                if flag2==1:
                    dp[l+1][j-1]+=dp[l][j]
                    flag2=0
                elif i & bit:
                    dp[l+1][j+1]+=dp[l][j]
                    flag2=1
                else:
                    dp[l+1][j]+=dp[l][j]
            for j in range(w):
                dp[l+1][j]%=mod
# print(dp)
print(dp[h][k-1]%mod)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
h,w,k=map(int,input().split())
n=2**(w-1)
haji=[0,0]
tyuo=[0,0,0]
if w==1:
    print(1)
    exit()
for i in range(n):
    flag=0
    for j in range(w-1):
        bit=1<<j
        if i & bit and i & (bit<<1):
            flag=1
        
    if flag==0:
        if i & 1:
            haji[0]+=1
        else:
            haji[1]+=1
        if w>2:
            if i & 1:
                tyuo[2]+=1
            elif i & 2:
                tyuo[0]+=1
            else:
                tyuo[1]+=1
haji.reverse()
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1

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

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

pt1 = [0, 0, 1]
pt2 = [0, 0, 1]
pt  = [1, 1, 2]

for i in range(8):
  p1 = pt2[-1]
  p2 = pt1[-1] + pt2[-1]
  pt1.append(p1)
  pt2.append(p2)
  pt.append(p1 + p2)
#print(pt)

L = [[[0 for _ in range(W + 1)] for _ in range(W + 1)] for _ in range(H)]
for i in range(1, W + 1):
  for j in range(1, W + 1):
    if abs(i - j) < 2 and j == K:
      ii, jj = min(i, j), max(i, j)
      L[0][i][j] = (pt[ii - 1] * pt[W - jj]) % MOD
#print(L)

for i in range(1, H):
  cnt = [sum(L[i - 1][j]) for j in range(W + 1)]
  #print("cnt:", cnt)
  
  for j in range(1, W + 1):
    for k in range(1, W + 1):
      if abs(j - k) < 2:
        jj, kk = min(j, k), max(j, k)
        L[i][j][k] += (cnt[k] * pt[jj - 1] * pt[W - kk])
        L[i][j][k] %= MOD
  #print(L[i])
  
cnt = [sum(L[H - 1][j]) for j in range(W + 1)]
#print("cnt:", cnt)
print(cnt[1])

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
if w==1:
    print(1)
    exit()
for i in range(h):
    for b in range(2**(w-1)):
        if "11" in bin(b):
            continue
        b*=2
        for j in range(w):
            if b&(1<<j):
                dp[i+1][j-1]+=dp[i][j]
            elif   b&(1<<(j+1)):
                dp[i+1][j+1] += dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                

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

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
    for b in range(2**(w-1)):
        if "11" in bin(b):
            continue
        b*=2
        for j in range(w):
            if b&(1<<j):
                dp[i+1][j-1]+=dp[i][j]
            elif   b&(1<<(j+1)):
                dp[i+1][j+1] += dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
                

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

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
dp=[[0]*w for _ in range(h+1)]
dp[0][0]=1
mod=10**9+7
for i in range(h):
    for b in range(2**(w-1)):
        if "11" in bin(b):
            continue
        for j in range(w):
            if b&(1<<j):
                dp[i][j-1]+=dp[i][j]
                dp[i+1][j-1]=dp[i][j-1]%mod
            elif   b&(1<<(j+1)):
                dp[i][j+1] += dp[i][j]
                dp[i+1][j+1]=dp[i][j+1]%mod
            else:
                dp[i+1][j] = dp[i][j]
                

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

Submission status: Wrong Answer

Solution code:
"""
21:12:30
"""
mod = 10**9 + 7
H, W, K = map(int, input().split())
# 残っている本数
bs = [1,2,3,5,7,10,13]

if W == 1:
    print(1)
    exit()
dp = [[0]*(W) for i in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        # 左端 : そのまま下ろす(j+1からｱﾐﾀﾞ)か、一つ右から下ろす(j+2からｱﾐﾀﾞ)
        if j == 0:
            dp[i+1][j] = dp[i][j] * bs[W-1-(j+1)] + dp[i][j+1] * bs[W-1-(j+2)]        
        # 右端 : そのまま下ろす(j-1からｱﾐﾀﾞ)か、一つ左から下ろす(j-2からｱﾐﾀﾞ)
        elif j == W-1:
            dp[i+1][j] = dp[i][j-1] * bs[j-2] + dp[i][j] * bs[j-1]   
        # 中    
        else:
            dp[i+1][j] = dp[i][j-1]*bs[max(0,j-2)]*bs[W-1-(j+1)] + dp[i][j]*bs[j-1]*bs[W-1-(j+1)] + dp[i][j+1]*bs[j-1]*bs[max(0,W-1-(j+2))]
        # print(dp[i+1])
        dp[i+1][j] %= mod
print(dp[H][K-1])