Problem:


Score: 400 points

Problem Statement

Amidakuji is a traditional method of lottery in Japan.

To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.

A valid amidakuji is an amidakuji that satisfies the following conditions:

No two horizontal lines share an endpoint.

The two endpoints of each horizontal lines must be at the same height.

A horizontal line must connect adjacent vertical lines.

Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.

For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.

Constraints

H is an integer between 1 and 100 (inclusive).

W is an integer between 1 and 8 (inclusive).

K is an integer between 1 and W (inclusive).

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

1 3 2

Sample Output 1

1

Only the following one amidakuji satisfies the condition:

Sample Input 2

1 3 1

Sample Output 2

2

Only the following two amidakuji satisfy the condition:

Sample Input 3

2 3 3

Sample Output 3

1

Only the following one amidakuji satisfies the condition:

Sample Input 4

2 3 1

Sample Output 4

5

Only the following five amidakuji satisfy the condition:

Sample Input 5

7 1 1

Sample Output 5

1

As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.

Sample Input 6

15 8 5

Sample Output 6

437760187

Be sure to print the answer modulo 1\ 000\ 000\ 007.



Sample input:
1 3 2


Sample output:
1

Submission status: Accepted

Solution code:
import itertools


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

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

mod = 10**9 + 7
path = [[i, i+1] for i in range(w-1)]
DP = [[0]*(h+1) for _ in range(w)]
DP[0][0] = 1

for height in range(h):
    for pos in range(w):
        down_unable = {pos}
        left_unable = {pos-1, pos}
        right_unable = {pos, pos+1}

        down_count = 1
        left_count = 1
        right_count = 1
        for pick in range(1, 1 + w//2):
            all_pattern = list(itertools.combinations(path, pick))

            for pattern in all_pattern:
                check = set()
                possible = True
                for a, b in pattern:
                    if check & {a, b}:
                        possible = False
                        break
                    check |= {a, b}
                if not possible:
                    continue
                if not check & down_unable:
                    down_count += 1
                if not check & left_unable:
                    left_count += 1
                if not check & right_unable:
                    right_count += 1

        if pos == 0:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod

        elif pos == w-1:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod
        else:
            DP[pos][height+1] += DP[pos][height] * down_count % mod
            DP[pos+1][height+1] += DP[pos][height] * right_count % mod
            DP[pos-1][height+1] += DP[pos][height] * left_count % mod

print(DP[k-1][h] % mod)

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w, K = list(map(int, readline().split()))
    if w == 1:
        print(1)
    else:
        pt = [[0] * w for _ in range(w)]
        pf = [0] * w
        for it in itertools.product([True, False], repeat=w-1):
            b = True
            for i in range(1, len(it)):
                if it[i] and it[i-1]:
                    b = False
                    break
            if b:
                for i in range(len(it)):
                    if it[i]:
                        pt[i][i+1] += 1
                        pt[i+1][i] += 1
                    else:
                        if i == 0:
                            pf[i] += 1
                        elif i == w - 2:
                            pf[i+1] += 1
                for i in range(1, w - 1):
                    if not it[i-1] and not it[i]:
                        pf[i] += 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):
                for k in range(w):
                    if j != k:
                        dp[i][j] += dp[i-1][k] * pt[j][k]
                    else:
                        dp[i][j] += dp[i-1][k] * pf[j]
                    dp[i][j] %= mod
        print(dp[-1][K-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    h,w,k=map(int,input().split())
    mod = 10**9+7
    b = [1,1,2,3,5,8,13,21,34]
    dp=[[0 for _ in range(w)]for j in range(h+1)]
    dp[0][0] = 1
    if w == 1:
        return 1

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

print(main())

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MOD = 10**9+7
dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
ls = []
for h in range(2**(W-1)):
  log = ''
  flag = True
  for x in range(W-1):
    if h%2==1 and flag:
      log += '1'
      flag = False
    else:
      log += '0'
      flag = True
    h >>= 1
  ls += [log]
if W==1:
  ls = ['0']
ls = set(ls)
for i in range(H):
  for j in range(W):
#    print(dp[-1], j)
    for log in ls:
      if j==0:
        if log[j]=='1':
          dp[i+1][j+1] += dp[i][j]%MOD
        else:
          dp[i+1][j] += dp[i][j]%MOD
      elif j==W-1:
        if log[j-1]=='1':
          dp[i+1][j-1] += dp[i][j]%MOD
        else:
          dp[i+1][j] += dp[i][j]%MOD
      else:
        if log[j-1]=='1':
          dp[i+1][j-1] += dp[i][j]%MOD
        elif log[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)

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict
import copy

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = 10 ** 9 + 7

#処理内容
def main():
	H, W, K = getlist()
	A = [0] * W
	A[0] = 1
	if W == 1:
		print(1)
	else:		
		for i in range(H):
			B = [0] * W
			for j in range(1 << (W - 1)):
				output = [0] * (W - 1)
				for k in range(W - 1):
					if ((j >> k) & 1) == 1:
						output[k] = 1
				judge = "Yes"
				for k in range(W - 2):
					if output[k] == 1 and output[k + 1] == 1:
						judge = "No"
				if judge == "Yes":
					if output[0] == 1:
						B[0] += A[1]
					else:
						B[0] += A[0]
					for k in range(1, W - 1):
						if output[k - 1] == 1:
							B[k] += A[k - 1]
						elif output[k] == 1:
							B[k] += A[k + 1]
						else:
							B[k] += A[k]
					if output[W - 2] == 1:
						B[W - 1] += A[W - 2]
					else:
						B[W - 1] += A[W - 1]

			for i in range(W):
				B[i] %= INF
			A = copy.deepcopy(B)
		print(A[K - 1] % INF)
	
if __name__ == '__main__':
	main()

Submission status: Accepted

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

dp = [[0] * (W + 2) for _ in range(H + 1)]  # dp[h][w] = 上からh本通った後にwにいるパターン数
dp[0][1] = 1

preCnt = [0] * (W + 1)  # w本を任意に引けるときの数
for w in range(1, W + 1):
    cnt = 0
    for bit in range(1 << w):
        if bin(bit).count('11') == 0:
            cnt += 1
    preCnt[w] = cnt

def left(w):
    ret = 1
    ret *= preCnt[w - 3] if w - 3 > 0 else 1
    ret *= preCnt[W - w - 1] if W - w - 1 > 0 else 1
    return ret % MOD

def right(w):
    ret = 1
    ret *= preCnt[w - 2] if w - 2 > 0 else 1
    ret *= preCnt[W - w - 2] if W - w - 2 > 0 else 1
    return ret % MOD

def mid(w):
    ret = 1
    ret *= preCnt[w - 2] if w - 2 > 0 else 1
    ret *= preCnt[W - w - 1] if W - w - 1 > 0 else 1
    return ret % MOD

for h in range(1, H + 1):
    for w in range(1, W + 1):
        dp[h][w] += dp[h - 1][w - 1] * left(w)
        dp[h][w] += dp[h - 1][w] * mid(w)
        dp[h][w] += dp[h - 1][w + 1] * right(w)
        dp[h][w] %= MOD

print(dp[H][K])

Submission status: Accepted

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

D = [[0]*W for _ in range(W)]
for S in range(1<<W-1):
    if S & S<<1 != 0:
        continue
    #print(bin(S))
    S <<= 1
    for i in range(W):
        if S>>i&1:
            D[i][i-1] += 1
        elif S>>i+1&1:
            D[i][i+1] += 1
        else:
            D[i][i] += 1
    #for d in D:
    #    print(d)

E = [[0]*W for _ in range(W)]
for i in range(W):
    E[i][i] = 1

for i in range(H):
    A = [[0]*W for _ in range(W)]
    for x in range(W):
        for y in range(W):
            A[x][y] = sum(E[x][z] * D[z][y] % mod for z in range(W)) % mod
    E = A

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

Submission status: Accepted

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

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

Submission status: Accepted

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


#dp[h][k]
bits = []
for i in range(2**(w-1)):
    bit = [0] * (w-1)
    for j in range(w-1):
        if ((i >> j) & 1):
            bit[j] = 1
    for j in range(w-2):
        if bit[j] == 1 and bit[j+1] == 1:
            break
    else:
        bits.append(bit)

path = [[0 for i in range(w)] for i in range(w)]

for bit in bits:
    for ww in range(w):
        flag = True
        if ww != w-1:
            if bit[ww] == 1:
                flag = False
                path[ww][ww+1] += 1
        if ww != 0:
            if bit[ww-1] == 1:
                flag = False
                path[ww][ww-1] += 1
        if flag:
            path[ww][ww] += 1

            
dp = [[0 for ww in range(w)] for hh in range(h+1)]

dp[0][0] = 1

for hh in range(h):
    for ww in range(w):
        for ww2 in range(w):
            dp[hh+1][ww2] += dp[hh][ww] * path[ww][ww2] 
            dp[hh+1][ww2] %= 1000000007
            
print(dp[-1][k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def check(x):
    n=x.bit_length()
    for i in range(n-1):
        if((x>>i)&1 and (x>>(i+1))&1):
            return False
    return True

def resolve():
    H,W,K=map(int,input().split())
    K-=1
    dp=[0]*W
    dp[0]=1
    for _ in range(H):
        ndp=[0]*W
        # 各 2^(W-1)通りの線の引き方から、dpの遷移先を考える
        for V in range(2**(W-1)):
            if(not check(V)): continue
            for w in range(W):
                if(w<W-1 and (V>>w)&1): # 右に線があるとき
                    ndp[w+1]+=dp[w]
                    ndp[w+1]%=MOD
                elif(w>0 and (V>>(w-1))&1): # 左に線があるとき
                    ndp[w-1]+=dp[w]
                    ndp[w-1]%=MOD
                else: # 双方に線がないとき
                    ndp[w]+=dp[w]
                    ndp[w]%=MOD
        dp=ndp
    print(dp[K])
resolve()

Submission status: Accepted

Solution code:
MOD = 1000000007
 
def get_fibonatti_table(n):
    table = [1,1]
    for i in range(2, n+1):
        table.append(table[i-1]+table[i-2])
    return table

def solve():
    H,W,K = map(int, input().split())
    fib_table = get_fibonatti_table(W)
    dp_table = [[0 for _ in range(W+1)] for _ in range(H+1)]
    dp_table[0][1] = 1
    for h in range(1, H+1):
        for w in range(1,W+1):
            weight = fib_table[w-1]*fib_table[W-w]
            dp_table[h][w] = dp_table[h-1][w] * weight
            if 1 < w:
                # w-1を足す
                weight = fib_table[w-2]*fib_table[W-w]
                # print(w,weight)
                dp_table[h][w] += dp_table[h-1][w-1] * weight
            if w < W:
                # w+1を足す
                weight = fib_table[w-1]*fib_table[W-w-1]
                dp_table[h][w] += dp_table[h-1][w+1] * weight
                
    # print(dp_table)
    print(dp_table[H][K] % MOD)
    
solve()

Submission status: Accepted

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[0]) % MOD
        elif j == (W-1):
            dp[i][j] = (dp[i-1][j] * (limit - num_lad[ladder-1]) + 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: Accepted

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

def dsf(i,v):
  if i==w-1:
    t = list()
    for j in range(0,w):
      t.append(j)
    for j in range(w-1):
      if v & 2**(j):
        t[j],t[j+1]=t[j+1],t[j]
    for x in range(w):
      a[x][t[x]] += 1
    l.append(v)
  else:
    dsf(i+1,v)
    if v & 2**(i-1) == 0:
      dsf(i+1,v | 2**i)

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

dsf(1,0)
dsf(1,1)

t=[[0 for i in range(w)] for j in range(2)]
t[0][0]=1

for i in range(h):
  for j in range(w):
    t[(i+1)%2][j] = 0
    t[i%2][j] %= mod
  for j in range(w):
    for x in range(w):
     t[(i+1)%2][x] += t[i%2][ｊ] * a[j][x]

print(t[h%2][k-1]%mod)

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

pattern = []
for i in range(1 << (W - 1)) :
    if '11' in bin(i) :
        continue
    pattern.append(i)

for _ in range(H) :
    dp_ = [0] * W
    for p in pattern :
        for i in range(W) :
            if i != W - 1 and p & (1 << i) :
                dp_[i+1] += dp[i]
                dp_[i+1] %= mod
            elif i != 0 and p & (1 << (i - 1)) :
                dp_[i-1] += dp[i]
                dp_[i-1] %= mod
            else :
                dp_[i] += dp[i]
                dp_[i] %= mod
    
    dp = dp_
    
print(dp[K-1])

Submission status: Accepted

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

f_dic = {}
def f(x):
    if x in f_dic:
        return f_dic[x]
    elif x == 0:
        f_dic[0]=1
        return f_dic[0]
    elif x == 1:
        f_dic[1]=1
        return f_dic[1]
    else:
        f_dic[x] = f(x-1)+f(x-2)
        return f_dic[x]


if W == 1:
    print(1)

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

Submission status: Accepted

Solution code:
MOD = int(1e9 + 7)

sizeI, sizeJ, targetJ = map(int, input().split())

validRows = [row for row in range(1 << (sizeJ - 1)) if '11' not in bin(row)]
# dp[i][j] - number of ways to come to position (i, j)
dp = [[0 for _ in range(sizeJ)] for _ in range(sizeI + 1)]
dp[0][0] = 1
for i in range(1, sizeI + 1):
    for j in range(sizeJ):
        for prevRow in validRows:
            if j - 1 >= 0 and (prevRow >> (j - 1)) & 1:
                dp[i][j] += dp[i - 1][j - 1]
            elif (prevRow >> j) & 1:
                dp[i][j] += dp[i - 1][j + 1]
            else:
                dp[i][j] += dp[i - 1][j]
            dp[i][j] %= MOD
print(dp[sizeI][targetJ - 1])

Submission status: Accepted

Solution code:
f=[0,1,1,2,3,5,8,13,21,34,55,89];h,w,k=map(int,input().split());a=[0]*(w+2);a[1]=1
for i in range(h):a=[0]+[(f[j-1]*f[w-j+1]*a[j-1]+f[j]*f[w-j+1]*a[j]+f[j]*f[w-j]*a[j+1])%(10**9+7)for j in range(1,w+1)]+[0]
print(a[k])

Submission status: Accepted

Solution code:
H, W, K = list(map(int, input().split(' ')))
# mat[i][j] = mat[i-1][j-1] * hoge + mat[i-1][j-1] * fuga + mat[i+1][j-1] * piyo
# hoge, fuga, piyo は隣接していない自由に置いて良い | | | ... | で固定値で決まる
# |-| -> hoge(2)=2
# |-|-| -> hoge(3)=3
# |-|-|-| -> hoge(4)=5
# |-|-|-|-| -> hoge(5)=8
# |-|-|-|-|-| -> hoge(6)=13
# |-|-|-|-|-|-| -> hoge(7)=21?
mat = []
for i in range(H+1):
    mat.append([0] * (W))
mat[0][0] = 1

def get(h, w):
    if h < 0 or w < 0:
        return 0
    if h >= H or w >= W:
        return 0
    return mat[h][w]

def hoge(w):
    d={1:1, 2:2, 3:3, 4:5, 5:8, 6:13, 7:21}
    return d.get(w, 1)

for i in range(1,H+1):
    for j in range(W):
        mat[i][j] = get(i-1, j-1) * hoge(j-1) * hoge(W-j-1) +\
                    get(i-1, j)   * hoge(j)   * hoge(W-j-1) +\
                    get(i-1, j+1) * hoge(j)   * hoge(W-j-1-1)
print(mat[H][K-1] % 1000000007)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
mod = 1000000007

def mul(a, b):
    newmatrix = [[0] * w for _ in range(w)]
    for i in range(w):
        for j in range(w):
            newmatrix[i][j] = sum(a[i][k] * b[k][j] for k in range(w)) % mod
    return newmatrix

matrix = [[0] * w for _ in range(w)]
for b in range(1 << (w - 1)):
    valid = True
    for i in range(w - 1):
        if (b >> i) & 3 == 3:
            valid = False
    if valid:
        for i in range(w):
            if (b >> i) & 1 != 0:
                matrix[i][i + 1] += 1
            elif i > 0 and (b >> (i - 1)) & 1 != 0:
                matrix[i][i - 1] += 1
            else:
                matrix[i][i] += 1

ret = [[1 if i == j else 0 for i in range(w)] for j in range(w)]
while h > 0:
    if h & 1 == 1:
        ret = mul(ret, matrix)
    matrix = mul(matrix, matrix)
    h //= 2

print(ret[0][k - 1])

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
dp = [1] + [0] * (w - 1)
mod = 1000000007
for _ in range(h):
    newdp = [0] * w
    for b in range(1 << (w - 1)):
        valid = True
        for i in range(w - 1):
            if (b >> i) & 3 == 3:
                valid = False
        if valid:
            for i in range(w):
                if (b >> i) & 1 != 0:
                    newdp[i + 1] = (newdp[i + 1] + dp[i]) % mod
                elif i > 0 and (b >> (i - 1)) & 1 != 0:
                    newdp[i - 1] = (newdp[i - 1] + dp[i]) % mod
                else:
                    newdp[i    ] = (newdp[i    ] + dp[i]) % mod
    dp = newdp
print(dp[k - 1])

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
mod = 10**9+7
g = [[0]*3 for _ in range(w)]
for bit in range(1<<(w-1)):
  f = 0
  for i in range(w-2):
    if bit & (3<<i) == 3<<i:
      f = 1
      break
  if f:
    continue
  neu = [1]*w
  for i in range(w-1):
    if bit&(1<<i):
      g[i][2] += 1
      g[i+1][0] += 1
      neu[i] = 0; neu[i+1] = 0
    g[i][1] += neu[i]
  g[-1][1] += neu[-1]
g = [[0]*3] + g + [[0]*3]
ol = [0]*(w+2)
ol[k] = 1
for _ in range(h):
  new = [0]*(w+2)
  for i in range(1,w+1):
    new[i] = (ol[i-1]*g[i-1][2] + ol[i]*g[i][1] + ol[i+1]*g[i+1][0])%mod
  ol = new
print(ol[1])

Submission status: Accepted

Solution code:
import sys


H,W,K = [int(_) for _ in input().split()]
l = []
c = 0
if W == 1:
    print(1)
    sys.exit()
#0本
l.append([0 for _ in range(W-1)])
#1本
for i in range(0, W-1):
    a = [0 for _ in range(W-1)]
    for j in range(0, W-1):
        if j == i:
            a[j] = 1
        else:
            a[j] = 0
    l.append(a)
#2本
if W >= 4:
    for i in range(0, W-3):
        for j in range(i+2, W-1):
            a = [0 for _ in range(W-1)]
            for k in range(0, W-1):
                if k == i or k == j:
                    a[k] = 1
                else:
                    a[k] = 0
            l.append(a)
#3本
if W >= 6:
    for i in range(0, W-5):
        for j in range(i+2, W-3):
            for k in range(j+2, W-1):
                a = [0 for _ in range(W-1)]
                for p in range(W-1):
                    if p == i or p == j or p == k:
                        a[p] = 1
                    else:
                        a[p] = 0
                l.append(a)
#4本
if W == 8:
    l.append([1,0,1,0,1,0,1])


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

for i in range(0, H):
    for j in range(0,W):
        for k in range(len(l)):
            q = HW[i][j]
            if j == 0:
                if l[k][j] == 1:
                    HW[i+1][j+1] += q
                else:
                    HW[i+1][j] += q
            elif j == W-1:
                if l[k][j-1] == 1:
                    HW[i+1][j-1] += q
                else:
                    HW[i+1][j] += q
            else:
                if l[k][j] == 0 and l[k][j-1] == 0:
                    HW[i+1][j] += q
                elif l[k][j] == 1:
                    HW[i+1][j+1] += q
                else:
                    HW[i+1][j-1] += q
        for x in range(0, W):
            HW[i+1][x] = HW[i+1][x] % 1000000007
  
ans = HW[H][K-1]

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
mod=10**9+7
dp=[[0]*w for i in range(h+1)]
dp[0][0]=1
data=[]
for i in range(2**(w-1)):
    for j in range(1,w-1):
        if (i>>j)&1==(i>>j-1)&1 and (i>>j)&1==1:
            break
    else:
        data.append(i)
for i in range(1,h+1):
    for u in data:
        if u&1==1:
            dp[i][0]=(dp[i][0]+dp[i-1][1])%mod
        else:
            dp[i][0]=(dp[i][0]+dp[i-1][0])%mod
        if w>1:
            if (u>>w-2)&1==1:
                dp[i][w-1]=(dp[i][w-1]+dp[i-1][w-2])%mod
            else:
                dp[i][w-1]=(dp[i][w-1]+dp[i-1][w-1])%mod
        for j in range(1,w-1):
            if (u>>j-1)&1==1:
                dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod
            elif (u>>j)&1==1:
                dp[i][j]=(dp[i][j]+dp[i-1][j+1])%mod
            else:
                dp[i][j]=(dp[i][j]+dp[i-1][j])%mod
print(dp[h][k-1])

Submission status: Accepted

Solution code:
import copy

def f(n):
    if n==0:
        return 1
    elif n==1:
        return 2
    else:
        return f(n-1)+f(n-2)

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

if W==1:
    ans=1
else:
    d={}
    for i in range(8):
        d[i]=f(i)
    d[-1]=d[-2]=d[-3]=1

    b=[0 for i in range(W+2)]
    a=[0 for i in range(W+2)]

    b[1]=d[W-2];b[2]=d[W-3]

    for i in range(H-1):
        for k in range(1,W+1):
            a[k]=b[k-1]*d[k-3]*d[W-k-1]
            a[k]+=b[k]*d[k-2]*d[W-k-1]
            a[k]+=b[k+1]*d[k-2]*d[W-k-2]
            a[k]%=p
        b=copy.copy(a)
    
    ans=b[K]

print(ans)

Submission status: Accepted

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)&3 == 3:
                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: Accepted

Solution code:
h, w, k = map(int, input().split())
a = [0]*(w-1) + [0,1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*(w+1)
tmp = [0]*(w+1)
dp[0] = 1
for _ in range(1, h+1):
    for i in range(w):
        tmp[i] = (dp[i]*a[i-1]*a[w-i-2]
            + dp[i+1]*a[i-1]*a[w-i-3]
            + dp[i-1]*a[i-2]*a[w-i-2]) % (10**9+7)
    dp, tmp = tmp, dp
print(dp[k-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
 
    h,w,k = map(int,input().split())
    mod = 10**9+7
 
    if w == 1:
        print(1)
        return
 
    fib = [1,2,3,5]
    for i in range(100):
        fib.append(fib[len(fib)-1]+fib[len(fib)-2])
    fib.append(1)
    fib.append(1)
    fib.append(1)
 
 
    dp = [[0]*w for _ in [0]*h]
    dp[0][0] = fib[w-2]
    dp[0][1] = fib[w-3]
 
    for i in range(1,h):
        for j in range(w):
            dp[i][j] = (dp[i-1][j]*fib[j-1]*fib[w-2-j])%mod
            if j >= 1:
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]*fib[j-2]*fib[w-2-j])%mod
            if j <= w-2:
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]*fib[j-1]*fib[w-3-j])%mod
    
    print(dp[-1][k-1])
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

if W == 1:
    print(1)
else:
    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
            if b[-1] == "0":
                dp[k+1][-1] += dp[k][-1]
                dp[k+1][-1] %= mod
    print(dp[H][K-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    if w == 1:
        print(1)
        return

    fib = [1,2,3,5]
    for i in range(100):
        fib.append(fib[len(fib)-1]+fib[len(fib)-2])
    fib.append(1)
    fib.append(1)
    fib.append(1)


    dp = [[0]*w for _ in [0]*h]
    dp[0][0] = fib[w-2]
    dp[0][1] = fib[w-3]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
H, W, K = map(int, input().split())
dp = [[0]*W for j in range(H+1)]
dp[0][0] = 1
if W == 1:
    print(1)
    exit()
for i in range(1, H+1):
    for j in range(1<<(W-1)):
        if any((j>>k) & 1 and j>>((k+1)) & 1 for k in range(W-2)):
            continue
        if j&1:
            dp[i][0] += dp[i-1][1]
        else:
            dp[i][0] += dp[i-1][0]
        dp[i][0] %= mod
        for k in range(1, W-1):
            if (j>>k)&1:
                dp[i][k]+= dp[i-1][k+1]
            elif (j>>(k-1))&1:
                dp[i][k]+= dp[i-1][k-1]
            else:
                dp[i][k]+=dp[i-1][k]
            dp[i][k] %= mod
        if (j>>(W-2))&1:
            dp[i][W-1] += dp[i-1][W-2]
        else:
            dp[i][W-1] += dp[i-1][W-1]
        dp[i][W-1] %= mod           
print(dp[H][K-1])

Submission status: Accepted

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

def main():
    H, W, K = map(int, input().split())
    fib = [1, 1]
    for i in range(W-2):
        fib.append(fib[-2] + fib[-1])
    
    nex = [[0] * W for i in range(W)]
    for i in range(W):
        nex[i][i] = fib[i] * fib[W-1-i]
        if i > 0:
            nex[i][i-1] = fib[i-1] * fib[W-i-1]
        if i < W-1:
            nex[i][i+1] = fib[i] * fib[W-i-2]
    MOD = int(1e9) + 7
    dp = [[0] * W for i in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            dp[i+1][j] += dp[i][j] * nex[j][j]
            dp[i+1][j] %= MOD
            if j > 0:
                dp[i+1][j-1] += dp[i][j] * nex[j][j-1]
                dp[i+1][j-1] %= MOD
            if j < W-1:
                dp[i+1][j+1] += dp[i][j] * nex[j][j+1]
                dp[i+1][j+1] %= MOD
    print(dp[H][K-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mapping = defaultdict(int)

for source in range(1 << (W - 1)):
    l = [False for _ in range(W - 1)]
    for i in range(W - 1):
        l[i] = bool(source & (1 << i))
    flag = True
    for i in range(W - 2):
        if l[i] and l[i + 1]:
            # invalid
            flag = False
            # print("break",l)
            break
    if not flag:
       continue

    for i in range(W):
        if i > 0 and l[i - 1]:  # decrement
            mapping[i, i - 1] += 1
        elif i < W - 1 and l[i]:  # increment
            mapping[i, i + 1] += 1
        else:
            mapping[i, i] += 1

last = [1] + [0] * (W - 1)
for _ in range(H):
    current = [0] * W
    for (start, dst), count in mapping.items():
        current[dst] += last[start] * count
        current[dst] = current[dst] % (10**9+7)
    last = current
print(last[K - 1] %(10**9+7))