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:
h,w,k = map(int, input().split())

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

case = []

def createCase(s):
    if (len(s) == w-1):
        case.append(s)
        return
    if len(s) != 0 and s[-1] == "1" :
        createCase(s+"0")
    else:
        createCase(s+"0")
        createCase(s+"1")

createCase("")

for i in range(len(case)):
    case[i] = "0"+case[i]+"0"

# print(case)

move = [[0]*3 for _ in range(w)]

for i in range(w):
    for j in case:
        if j[i] == j[i+1] == "0":
            move[i][1] += 1
        if j[i+1] == "1":
            move[i][2] += 1
        if j[i] == "1":
            move[i][0] += 1

# print(move)

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

fib = [0, 1, 2, 3, 5, 8, 13, 21]

dp[0][0] = fib[w-1]
dp[0][1] = fib[w-2]

for i in range(1, h):
    dp[i][0] = (dp[i-1][0]*move[0][1] + dp[i-1][1]*move[1][0]) % 1000000007
    for j in range(1, w-1):
        dp[i][j] = (dp[i-1][j]*move[j][1] + dp[i-1][j-1]*move[j-1][2] + dp[i-1][j+1]*move[j+1][0]) % 1000000007
    dp[i][-1] = (dp[i-1][-2]*move[-2][2] + dp[i-1][-1]*move[-1][1]) % 1000000007

# print(dp)

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

Submission status: Accepted

Solution code:
def run(H, W, K):
    # あみだくじの通る道のパターン
    dp = {(1, 0): 1}
    for w in range(2, W+1):
        dp[(w, 0)] = 0
    # ダミーで0とW+1には0を入れておく
    for h in range(0, H+1):
        dp[(0, h)] = 0
        dp[(W+1, h)] = 0
    # あみだくじの通る道のパターンを計算
    for h in range(1, H+1):
        for w in range(1, W+1):
            '''
            hの位置で他の線のパターンを計算
            w-1からwの線があるとき
            1からw-2までw-3本の線が引ける、w+1からWまでW-w-1本の線が引ける
            1本なら2パターン、2本なら3パターン、3本なら5パターン、4本なら1+4+3=8パターン
            5本なら1+5+6+1=13パターン、6本なら1+6+10+4=21、7本なら1+7+15+10+1=34パターン
            ''' 
            a = get_coef(w-3, W-w-1)
            b = get_coef(w-2, W-w-1)
            c = get_coef(w-2, W-w-2)
            dp[(w, h)] = (a*dp[(w-1, h-1)] + b*dp[(w, h-1)] + c*dp[(w+1, h-1)]) % 1000000007
    # あみだのKに行くための経路の合計
    return dp[K, H]


def get_coef(w_l, w_r):
    coef = [1, 2, 3, 5, 8, 13, 21, 34]
    if w_l < 0:
        w_l = 0
    if w_r < 0:
        w_r = 0
    return coef[w_l]*coef[w_r]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
fib = [0, 1, 1, 2, 3, 5, 8, 13, 21]
dp = [[0] * (w + 2) for i in range(h + 1)]
dp[0][1] = 1

for j in range(h):
    for l in range(1, w + 1):
        dp[j + 1][l] = fib[l] * fib[w - l + 1] * dp[j][l] + fib[l - 1] * fib[w - l + 1] * dp[j][l - 1] + fib[l] * fib[w - l] * dp[j][l + 1]

print(dp[h][k] % 1000000007)

Submission status: Accepted

Solution code:
from collections import Counter

H, W, K = [int(_) for _ in input().split()]

MOD = 1000000007

pats = [[0]]

for i in range(1, W):
    pats = [p + [i] for p in pats] + [p[:-1] + [i, i - 1] for p in pats if p[-1] == i - 1]

iws = [Counter(r) for r in zip(*pats)]

rs = [1] + [0] * (W - 1)

for j in range(H):
    rs = [sum(rs[i] * iw[i] for i in iw) % MOD for iw in iws]

print(rs[K - 1])

Submission status: Accepted

Solution code:
H, W, K = [int(_) for _ in input().split()]

MOD = 1000000007

pats = [[0]]

for i in range(1, W):
    pats = [p + [i] for p in pats] + [p[:-1] + [i, i - 1] for p in pats if p[-1] == i - 1]

rs = [1] + [0] * (W - 1)

for j in range(H):
    rs = [sum(rs[p[i]] for p in pats) % MOD for i in range(W)]

print(rs[K - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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())
mod = 10 ** 9 + 7
if w == 1:
  print(1)
  exit()
lis = [[0 for i in range(w)] for s in range(h+1)]
lis[0][0] = 1
dp1 = [0]
dp2 = [1]
for i in range(1,w-1):
  dp1.append(dp2[i-1])
  dp2.append(dp2[i-1] + dp1[i-1])
dp1.insert(0,0)
dp2.insert(0,0)
dp = [dp1[i] + dp2[i] for i in range(w)]
for i in range(h):
  for j in range(w):
    if j == 0 or j == w-1:num = dp[w-1]
    else:num = dp[j] * dp[w-j-1]
    lis[i+1][j] += num * lis[i][j] % mod
    if j != 0:
      lis[i+1][j-1] += max(1,dp[j-1]) * max(1,dp[w-j-1]) * lis[i][j] % mod
    if j != w-1:
      lis[i+1][j+1] += max(1,dp[j]) * max(1,dp[w-j-2]) * lis[i][j] % mod
print(lis[h][k-1] % mod)

Submission status: Accepted

Solution code:
MOD = 1000000007
H,W,K=map(int,input().split())
##Precalculation            
num = [[0 for _ in range(W)] for _ in range(W)]
for value in range(2**(W-1)):
    bit = [False for _ in range(W-1)]
    for d in range(W-1):
        bit[d] = (2**d & value) > 0
    duplicate = False
    for d in range(1,W-1):
        if bit[d] and bit[d-1]:
            duplicate = True
            break
    if duplicate:
        continue
    ##No Duplicate Assured
    for x in range(W):
        num[x][x] += 1
    for d in range(W-1):
        if bit[d]:
            num[d][d+1] += 1
            num[d+1][d] += 1
            num[d][d] -= 1
            num[d+1][d+1] -= 1
##Time to Dynamic Programming YEAHHHHHH##
dp = [[0 for _ in range(W)] for _ in range(H+1)]
dp[0][0] = 1
for h in range(1,H+1):
    for k in range(W):
        for j in range(W):
            dp[h][k] += (dp[h-1][j]*num[j][k])%MOD
            dp[h][k] %= MOD
print(dp[H][K-1])

Submission status: Accepted

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

bit = []
for i in range(1 << (W - 1)):
    flag = True
    for j in range(W - 1):
        if i & 1 << j and i & 1 << (j + 1):
            flag = False
            break

    if flag:
        bit.append(i)

MOD = 10 ** 9 + 7
dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in bit:
            ne = j
            if k & 1 << j:
                ne = j + 1
            elif j - 1 >= 0 and k & 1 << (j - 1):
                ne = j - 1

            dp[i + 1][ne] += dp[i][j]
            dp[i + 1][ne] %= MOD

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

Submission status: Accepted

Solution code:
def amida(arr, rest):
    num=0
    if rest<1:
        return 1

    num+=amida(arr, rest-2)
    arr[-rest-1]+=num
    num+=amida(arr, rest-1)
    return num

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

arr=[0 for i in range(W+2)]
arr[1]=1

line=[0 for i in range(W+1)]
sum_=amida(line,W-1)

for i in range(H):
    tmp=arr[:]
    for j in range(1,W+1):
        arr[j]=(tmp[j]*(sum_-line[j]-line[j-1])+tmp[j+1]*line[j]+tmp[j-1]*line[j-1])%(10**9+7)
print(arr[K])

Submission status: Accepted

Solution code:
from itertools import product
H, W, K = map(int, input().split())
A = [[0 for j in range(W+1)] for i in range(H+1)]
M = 10 ** 9 + 7
A[0][1] = 1


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

cache = {}


def xyz(x):
    x -= 2
    if cache.get(x) is not None:
        return cache[x]
    X, Y, Z = 0, 0, 0
    for i in product('01', repeat=W-1):
        s = ''.join(i)
        if s.find('11') != -1:
            continue
        if x == -1:
            if s[0] == '1':
                Z += 1
            else:
                Y += 1
            continue
        if W - 2 == x:
            if s[-1] == '1':
                X += 1
            else:
                Y += 1
            continue
        t = s[x:x+2]
        if t == '10':
            X += 1
        elif t == '01':
            Z += 1
        else:
            Y += 1
    cache[x] = (X, Y, Z)
    return X, Y, Z


for h in range(H+1):
    for x in range(1, W+1):
        if H < h + 1:
            continue
        X, Y, Z = xyz(x)
        A[h + 1][x - 1] += (X * A[h][x]) % M
        A[h + 1][x] += (Y * A[h][x]) % M
        if W < x + 1:
            continue
        A[h + 1][x + 1] += (Z * A[h][x]) % M


print(A[H][K] % M)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
li = [1]+[0]*(w-1)
if w == 1:
    print(1)
else:
    for i in range(h):
        t = li.copy()
        if w == 2:
            li[0] = (t[0] + t[1]) % 1000000007
            li[1] = (t[0] + t[1]) % 1000000007
        elif w == 3:
            li[0] = (2*t[0] + t[1]) % 1000000007
            li[1] = (t[0] + t[1] + t[2]) % 1000000007
            li[2] = (t[1] + 2 * t[2]) % 1000000007
        elif w == 4:
            li[0] = (3*t[0] + 2*t[1]) % 1000000007
            li[1] = (2*t[0] + 2*t[1] + t[2]) % 1000000007
            li[2] = (t[1] + 2*t[2] + 2*t[3]) % 1000000007
            li[3] = (2*t[2] + 3 * t[3]) % 1000000007
        elif w == 5:
            li[0] = (5 * t[0] + 3*t[1]) % 1000000007
            li[1] = (3 * t[0] + 3*t[1] + 2*t[2]) % 1000000007
            li[2] = (2 * t[1] + 4*t[2] + 2*t[3]) % 1000000007
            li[3] = (2 * t[2] + 3 * t[3] + 3 * t[4]) % 1000000007
            li[4] = (3 * t[3] + 5 * t[4]) % 1000000007
        elif w == 6:
            li[0] = (8 * t[0] + 5 * t[1]) % 1000000007
            li[1] = (5 * t[0] + 5 * t[1] + 3 * t[2]) % 1000000007
            li[2] = (3 * t[1] + 6 * t[2] + 4 * t[3]) % 1000000007
            li[3] = (4 * t[2] + 6 * t[3] + 3 * t[4]) % 1000000007
            li[4] = (3 * t[3] + 5 * t[4] + 5 * t[5]) % 1000000007
            li[5] = (5 * t[4] + 8 * t[5]) % 1000000007
        elif w == 7:
            li[0] = (13 * t[0] + 8 * t[1]) % 1000000007
            li[1] = (8 * t[0] + 8 * t[1] + 5 * t[2]) % 1000000007
            li[2] = (5 * t[1] + 10 * t[2] + 6 * t[3]) % 1000000007
            li[3] = (6 * t[2] + 9 * t[3] + 6 * t[4]) % 1000000007
            li[4] = (6 * t[3] + 10 * t[4] + 5 * t[5]) % 1000000007
            li[5] = (5 * t[4] + 8 * t[5] + 8 * t[6]) % 1000000007
            li[6] = (8 * t[5] + 13 * t[6]) % 1000000007
        else:
            li[0] = (21 * t[0] + 13 * t[1]) % 1000000007
            li[1] = (13 * t[0] + 13 * t[1] + 8 * t[2]) % 1000000007
            li[2] = (8 * t[1] + 16 * t[2] + 10 * t[3]) % 1000000007
            li[3] = (10 * t[2] + 15 * t[3] + 9 * t[4]) % 1000000007
            li[4] = (9 * t[3] + 15 * t[4] + 10 * t[5]) % 1000000007
            li[5] = (10 * t[4] + 16 * t[5] + 8 * t[6]) % 1000000007
            li[6] = (8 * t[5] + 13 * t[6] + 13 * t[7]) % 1000000007
            li[7] = (13 * t[6] + 21 * t[7]) % 1000000007
    print(li[k - 1])

Submission status: Accepted

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
for i in range(1,h+1): #高さ
    for p in range(2**(w-1)):
        bit = list(str(bin(p)))
        bit.pop(0)
        bit.pop(0)
        for a in range(w-1-len(bit)):
            bit.insert(0,"0")
        temp = True
        for a in range(w-2):
            if bit[a] == "1" and bit[a] == bit[a+1]:
                temp = False
        if temp:
            mix = [b for b in range(w)]
            for a in range(w-1):
                if bit[a] == "1":
                    mix[a],mix[a+1] = mix[a+1],mix[a]
            for b in range(w):
                dp[i][b] += dp[i-1][mix[b]]
                dp[i][b] = dp[i][b]%mod
print(dp[h][k-1])

Submission status: Accepted

Solution code:
H,W,K=[int(i) for i in input().split()]
Fn=[1,1,2,3,5,8,13,21,0]
ans=[]
ans0=[0 for i in range(W+2)]
ans0[1]=1
ans.append(ans0)
for i in range(1,H+1):
    ansi=[0 for i in range(W+2)]
    for j in range(1,W+1):
        ansi[j-1]+=ans[i-1][j]*Fn[j-2]*Fn[W-j]
        ansi[j]+=ans[i-1][j]*Fn[j-1]*Fn[W-j]
        ansi[j+1]+=ans[i-1][j]*Fn[j-1]*Fn[W-j-1]
    for j in range(W+2):
        ansi[j]%=1000000007
    ans.append(ansi)
print(ans[H][K])

Submission status: Accepted

Solution code:
H, W, K = [int(i) for i in input().split()]

validBit = []
for i in range(1<<(W-1)):
    valid = True
    for j in range(W-1):
        if ((i>>j)&1) == 1 and ((i>>(j+1))&1) == 1:
            valid = False
    if valid:
        validBit.append(i)

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

for i in range(H):
    for j in range(W):
        if dp[i][j] == 0:
            continue
        for k in validBit:
            nj = j
            if ((k >> j) & 1) == 1:
                nj = j + 1
            elif j > 0 and (k >> (j-1) & 1) == 1:
                nj = j - 1

            dp[i+1][nj] = (dp[i+1][nj] + dp[i][j])%mod

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

Submission status: Accepted

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

Submission status: Accepted

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

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

base = [[0] * W for _ in range(W)]

for bit in range(2 ** (W - 1)):
    temp = [(bit & (1 << i) != 0) for i in range(W - 1)]
    before = False
    is_ok = True
    for line in temp:
        if line:
            if before:
                is_ok = False
                break
            else:
                before = True
        else:
            before = False
    
    if is_ok:
        before = False
        for i, line in enumerate(temp):
            if line:
                base[i][i + 1] += 1
                base[i + 1][i] += 1
                before = True
            else:
                if not before:
                    base[i][i] += 1

                before = False

        if not temp[-1]:
            base[-1][-1] += 1
dp = [[0] * W for _ in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1, 1):
    for j in range(W):
        for k in range(W):
            dp[i][j] = (dp[i][j] + dp[i - 1][k] * base[k][j]) % mod

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

Submission status: Accepted

Solution code:
h,w,kk = map(int,input().split())
dp = [[[] for j in range(w)] for i in range(h+1)]
# dp[i][j]
# 高さiにおいて点jに行き得る通り数
for i in range(h+1):
        for j in range(w):
                dp[i][j] = 0
dp[0][0]=1
mod = 1000000007

for i in range(1,h+1):
        for j in range(1<<(w-1)):
                yoko = [False for loo in range(w)]
                for k in range((w-1)):
                        yoko[k] = True if ((j>>k)&1) else False
                
                ok = True
                for l in range(w-2):
                        if(yoko[l]==True and yoko[l+1]==True):
                                ok = False
                if(not ok):
                        continue
                
                for l in range(w):
                        if(l==0):
                                if(yoko[l]):
                                        dp[i][l] += dp[i-1][l+1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod
                                continue
                        if(l==w-1):
                                if(yoko[l-1]):
                                        dp[i][l] += dp[i-1][l-1]
                                else:
                                        dp[i][l] += dp[i-1][l]
                                dp[i][l]%=mod                                
                                continue

                        if(yoko[l-1] or yoko[l]):
                                if(yoko[l-1]):
                                        dp[i][l]+= dp[i-1][l-1]
                                else:
                                        dp[i][l]+= dp[i-1][l+1]
                        else:
                                dp[i][l] += dp[i-1][l]
                        dp[i][l]%=mod
                        
print(dp[h][kk-1])

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MODN = int(1e9+7)

# A[i][j] i=Hまでで、j=Kにいける通り数（MOD）
A = [[0] * (W+2) for i in range(H+1)]

A[0][1] = 1

# N本の縦棒にひとつの高さで引ける組み合わせ数
def multip(N):
  tempa = [1,1,1,2,3,5,8,13,21,34,55]
  return(tempa[N+1])
  
for i in range(1,H+1):
  for j in range(1,W+2):
    if j < 1 or j > W:
      A[i][j] = 0
    else:
      A[i][j] = (A[i-1][j-1]*(multip(j-2) * multip(W-j)) + A[i-1][j]*(multip(j-1) * multip(W-j))+ A[i-1][j+1]*(multip(j-1) * multip(W-j-1))) % MODN
      
print(A[H][K])

Submission status: Accepted

Solution code:
mod = 10**9+7

h,w,k = map(int,input().split())
fibonacchi =[1, 1, 2, 3, 5, 8, 13, 21, 34]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = 1
for i in range(h):
  for j in range(w+1):
    #dp[i][j]からdp[i+1][j-1]に遷移する条件
    #jとj-1の間に横棒がある&j-1とj-2の間、j+1とjの間に横棒がない
    #この置き方は
    #（縦棒1から縦棒j-2までの横棒の置き方）* （縦棒j+1から縦棒wまでの横棒の置き方置き方）
    if j >= 2:
      dp[i+1][j-1] += (fibonacchi[j-2]*fibonacchi[w-j])*dp[i][j]
      dp[i+1][j-1]%=mod

    #dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
    #j+1とjの間に横棒がある&jとj-1の間、j+2とj+1の間に横棒がない
    #この置き方は
    #(縦棒1から縦棒j-1の置き方)*(縦棒j+2*wまでの横棒の置き方)
    if j <= w-1:
      dp[i+1][j+1] += (fibonacchi[j-1]*fibonacchi[w-j-1])*dp[i][j]
      dp[i+1][j+1]%=mod

    #dp[i][j]からdp[i+1][j]への遷移が起こる条件は
    #j-1とjの間、jとj+1の間に横棒がない
    #このような横棒の置き方は
    #（縦棒1から縦棒j-1の置き方）*（縦棒j+1からwまでの棒の置き方）
    dp[i+1][j] += (fibonacchi[j-1]*fibonacchi[w-j])*dp[i][j]
    dp[i+1][j] %=mod

print(dp[h][k])

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**2)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print(1)
    else:
        print(0)
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [[1] + [0 for x in range(W-1)]] + [[0] * W for _ in range(N)]
for i in range(N):
    i += 1
    for j in range(W):
        d[i][j] = (d[i-1][j] * cc[j]) % mod
        if j != 0:
            d[i][j] = (d[i][j] + (d[i-1][j-1] * cccl[j]) )% mod
        if j != W-1:
            d[i][j] = (d[i][j] + (d[i-1][j+1] * cccr[j])) % mod

print(d[N][K-1])

Submission status: Accepted

Solution code:
mod = 10**9+7

h,w,k = map(int,input().split())
k = k-1
dp = [0]*1000 #dp[i]=i個縦棒がある時の横棒の引き方
dp[0]=1
dp[1]=1
dp[2]=2

for i in range(3,1000):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  #i-1とi番目に横棒を引かないとき、横棒の置き方は1からi-1番目の置き方と同じ
  #i-1とi番目に横棒を引くとき、横棒の置き方は1からi-2番目の置き方と同じ（i-1とi-2の間には置けないから）
  #→iの横棒の置き方はf(i-1)+f(i-2) ※場合わけにおける組み合わせ総数

dp2=[[0 for j in range(w)] for i in range(h+1)] #上からi下がったところでj番目にいく縦線を引くようなあみだくじの総数

dp2[0][0] = 1
for i in range(h):
  for j in range(w):
    #dp[i][j]からdp[i+1][j]への遷移が起こる条件は
    #j-1とjの間、jとj+1の間に横棒がない
    #このような横棒の置き方は
    #（縦棒1から縦棒j-1の置き方）*（縦棒j+1からwまでの棒の置き方）

    dp2[i+1][j] = (dp2[i+1][j]+dp2[i][j]*dp[j]%mod*dp[w-j-1]%mod)%mod

    #dp[i][j]からdp[i+1][j-1]に遷移する条件
    #jとj-1の間に横棒がある
    #j-1とj-2の間、j+1とjの間に横棒がない
    #この置き方は
    #（縦棒1から縦棒j-2までの横棒の置き方）* （縦棒jから縦棒wまでの横棒の置き方置き方）
    if (j-1>=0):
      dp2[i+1][j-1]=(dp2[i+1][j-1]+dp2[i][j]*dp[j-1]%mod*dp[w-j-1]%mod)%mod

    #dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
    #j+1とjの間に横棒がある
    #jとj-1の間、j+2とj+1の間に横棒がない
    #この置き方は
    #(縦棒1から縦棒j-1の置き方)*(縦棒j+2*wまでの横棒の置き方)

    if (j+1<w):
      dp2[i+1][j+1]=(dp2[i+1][j+1]+dp2[i][j]*dp[j]%mod*dp[w-j-2]%mod)%mod


print(dp2[h][k])

Submission status: Accepted

Solution code:
a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print(s[a][c-1]%(10**9+7))

Submission status: Accepted

Solution code:
from itertools import product


def violates(w_flags):
    prev_flag = w_flags[0]
    for flag in w_flags[1:]:
        if flag and prev_flag:
            return True
        prev_flag = flag
    return False


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

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

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

for h in range(1, H + 1):
    for w_flags in product((False, True), repeat=W-1):
        if violates(w_flags):
            continue
        for w in range(W):
            if w == 0:
                if w_flags[0]:
                    dp[h][0] += dp[h - 1][1]
                else:
                    dp[h][0] += dp[h - 1][0]
            elif w == W - 1:
                if w_flags[W - 2]:
                    dp[h][W - 1] += dp[h - 1][W - 2]
                else:
                    dp[h][W - 1] += dp[h - 1][W - 1]
            else:
                if w_flags[w - 1] == True:
                    dp[h][w] += dp[h - 1][w - 1]
                elif w_flags[w] == True:
                    dp[h][w] += dp[h - 1][w + 1]
                else:
                    dp[h][w] += dp[h - 1][w]
            dp[h][w] %= MOD

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
H, W, K = map(int, input().split())
MOD = 10**9 + 7
F = [1,1,2,3,5,8,13,21,34]
c1 = collections.Counter([1])

for i in range(H):
    tmp = collections.Counter()
    for c in c1:
        if c > 1:
            tmp[c-1] += c1[c] * F[max([0, c-2])] * F[W-c]

        tmp[c] += c1[c] * F[c-1] * F[W-c]

        if c < W:
            tmp[c+1] += c1[c] * F[c-1] * F[W-c-1]

    c1 = collections.Counter(tmp)
    # print('%d c1=%s'%(i+1,c1))

# print('c1=', c1)

ans = c1[K]
print(ans%MOD)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
mod = 7 + 10**9
No = [1 for i in range(7)] #使用しない辺の取り方
No[1], No[2], No[3], No[4] = 2, 3, 5, 8
No[5], No[6]= 13, 21

if W == 1:
    print(1)
else:
    DP = [[0 for w in range(W)] for h in range(H)]
    DP[0][0], DP[0][1] = No[max(0, W-2)], No[max(0, W-3)]
    for h in range(1, H):
        for w in range(W):
            if w == 0:
                left = 0
                up = DP[h-1][0] * No[max(0, W-2)] % mod
                right = DP[h-1][1] * No[max(0, W-3)] % mod
            elif w == W-1:
                left = DP[h-1][W-2] * No[max(0, W-3)] % mod
                up = DP[h-1][W-1] * No[max(0,W-2)] % mod
                right = 0
            else:
                left = DP[h-1][w-1] * No[max(0, w-2)] * No[max(0, W-w-2)] % mod
                up = DP[h-1][w] * No[max(0, w-1)] * No[max(0, W-w-2)] % mod
                right = DP[h-1][w+1] * No[max(0, w-1)] * No[max(0, W-w-3)] % mod
            DP[h][w] = (left+up+right) % mod
    print(DP[H-1][K-1])

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W, K = inpl()

if W == 1:
    print(1)
else:
    mod = 10**9 + 7
    S = [[0 for _ in range(W)] for _ in range(H+1)]
    S[0][0] = 1
    
    dpy = [0 for _ in range(W-1)]
    dpn = [0 for _ in range(W-1)]
    dpy[0] = 0
    dpn[0] = 1
    dpy = [0]
    dpn = [1]
    for i in range(1,W-1):
        dpy.append(dpn[i-1])
        dpn.append(dpn[i-1] + dpy[i-1])
    dpy = [0]+dpy
    dpn = [0]+dpn
    dp = [dpy[i] + dpn[i] for i in range(W)]
    for i in range(H):
       for j in range(W):
           if j == 0 or j == W-1:
               c = dp[W-1]
           else:
               c = dp[j]*dp[W-j-1]
           S[i+1][j] += c*S[i][j] % mod
           if  j != 0 :
              S[i+1][j-1] += max(1,dp[j-1])*max(1,dp[W-j-1])*S[i][j] %mod
           if j != W-1 :
               S[i+1][j+1] += max(1,dp[j])*max(1,dp[W-j-2])*S[i][j]  %mod
    print(S[H][K-1]%mod)

Submission status: Accepted

Solution code:
def main():
    """
    input:
        1 <= H <= 100
        1 <= W <= 8
        1 <= K <= W

    output:
        数列の項の最大公約数の最大値
    """
    H, W, K = map(int, input().split())

    # ans = f(H, W, K)
    ans = editorial(H, W, K)
    print(ans)


def editorial(H, W, K):
    mod = 10 ** 9 + 7
    dp = [[0] * W for _ in range(H+1)]
    dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            k_max = 1 << (W - 1)
            for k in range(k_max):
                # 2つの横線がつながっていないか
                ok = True
                for l in range(W - 2):
                    if k >> l & 1 and k >> (l + 1) & 1:
                        ok = False

                if not ok:
                    continue

                if j >= 1 and k >> (j - 1) & 1:  # left
                    a = j - 1
                elif j <= W - 2 and (k >> j) & 1:  # right
                    a = j + 1
                else:  # straight
                    a = j

                dp[i + 1][a] += dp[i][j]
                dp[i + 1][a] %= mod

    return dp[H][K - 1]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def d_number_of_amidakuji(H, W, K):
    # 参考: http://sigma1113.hatenablog.com/entry/2018/11/04/235700
    MOD = 10**9 + 7
    fibonacci = [1, 1, 2, 3, 5, 8, 13, 21, 34]  # W<=8なのでこれだけでいい

    # dp[i][j]: 上からi[cm]下がったところでj番目の縦線に行くようなあみだくじ数
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][1] = 1  # 1番からスタートする
    for i in range(H):
        for j in range(1, W + 1):
            if j >= 2:
                # dp[i][j]からdp[i+1][j-1]への遷移が起こる条件は
                # jとj-1の間に横棒がある
                # j-2とj-1の間、jとj+1の間に横棒がない
                # このような横棒の置き方は、
                # 縦線1から縦線j-2までの横棒の置き方 * 縦線j+1からWまでの横棒の置き方
                dp[i + 1][j - 1] += (fibonacci[j - 2] * fibonacci[W - j]) * dp[i][j]
                dp[i + 1][j - 1] %= MOD
            if j <= W - 1:
                # dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
                # jとj+1の間に横棒がある
                # j-1とjの間、j+1とj+2の間に横棒がない
                # このような横棒の置き方は、
                # 縦線1から縦線j-1までの横棒の置き方 * 縦線j+2からWまでの横棒の置き方
                dp[i + 1][j + 1] += (fibonacci[j - 1] * fibonacci[W - j - 1]) * dp[i][j]
                dp[i + 1][j + 1] %= MOD
            # dp[i][j]からdp[i+1][j+1]への遷移が起こる条件は
            # j-1とjの間、jとj+1の間に横棒がない
            # このような横棒の置き方は、
            # 縦線1から縦線j-1までの横棒の置き方 * 縦線j+1からWまでの横棒の置き方
            dp[i + 1][j] += (fibonacci[j - 1] * fibonacci[W - j]) * dp[i][j]
            dp[i + 1][j] %= MOD
    ans = dp[H][K]
    return ans

H, W, K = [int(i) for i in input().split()]
print(d_number_of_amidakuji(H, W, K))

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**2)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def erabu(aW):
    r = 0
    for i in range(aW // 2 + 1 + 1):
        sp = aW - (2*i -1)
        r += cmb(sp+i+1-1, sp, mod)
    return r

N, W, K = [int(x) for x in input().strip().split(" ")]
hasi = 0
cc = []
if W == 1:
    if K == 1:
        print(1)
    else:
        print(0)
    sys.exit()
elif W == 2:
    cccl = [1, 1]
    cc = [1, 1]
elif W == 3:
    cccl = [1, 1, 1]
    cc = [2, 1, 2]
elif W >= 4:
    aW = W - 1
    hW = aW - 2
    nhW = aW - 3
    cc = []
    cccl = []
    for w in range(W):
        nn = max(W - 1 - w - 1, 0)
        nnn = max((W - 1) - nn - 2, 0)
        if w == W -1:
            nnn += 1
        cc.append(erabu(nn) * erabu(nnn))
        cccl.append(erabu(nn) * erabu(nnn-1))

cccl[0] = 0
cccr = cccl[::-1]
d = [1] + [0 for x in range(W-1)]
for i in range(N):
    newd = []
    for j in range(W):
        newd.append(0)
        if j != 0:
            newd[j] = (newd[j] + (d[j-1] * cccl[j]) )% mod
        if j != W-1:
            newd[j] = (newd[j] + (d[j+1] * cccr[j])) % mod
        newd[j] = (newd[j] + (d[j] * cc[j])) % mod
    d = newd[:]

print(d[K-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)
b = [0]*(w+2)
a[1] = 1
for i in range(h):
  for j in range(1,w+1):
    b[j] =(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])%1000000007
  for j in range(1,w+1):
    a[j] = b[j]   
print(a[k])