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

def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

H, W, K = map(int, input().split())
seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i, W_i in itertools.product(range(1, H + 1), range(W)):
    if (W_i == 0):
        if(W == 1):
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
    elif (W_i == (W - 1)):
        dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
    else:
        dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Submission status: Accepted

Solution code:
def amida_counter(H_i_amida_list):
    counter = 0

    for amida_bin in range(2**len(H_i_amida_list)):
        if (("11" in format(amida_bin, "b")) == False):
            counter += 1

    return counter

def amida_number(left_amida, right_amida):
    left_counter = amida_counter(left_amida) if(len(left_amida) > 0) else 1
    right_counter = amida_counter(right_amida) if(len(right_amida) > 0) else 1

    return (left_counter * right_counter)

def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)
    left_x_amida = x_amida[:(W_i-2)] if(W_i-2 >= 0) else ""
    right_x_amida = x_amida[(W_i+1):]

    return amida_number(left_x_amida, right_x_amida)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)
    left_y_amida = y_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_y_amida = y_amida[W_i+1:]

    return amida_number(left_y_amida, right_y_amida)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)
    left_z_amida = z_amida[:W_i-1] if(W_i-1 >= 0) else ""
    right_z_amida = z_amida[W_i+2:]

    return amida_number(left_z_amida, right_z_amida)

H, W, K = map(int, input().split())
seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i in range(1, H + 1):
    for W_i in range(W):
        if (W_i == 0):
            if(W == 1):
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
            else:
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
        elif (W_i == (W - 1)):
            dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def calc_pattern_num(src, dst, W):
    if W == 1:
        if src == dst :
            return 1
        else:
            return 0

    count = 0
    for i in range(2**(W - 1)):
        is_OK = True
        for j in range((W - 1)):
            if j > 0:
                if ((i >> j) & 0x01)==1 and ((i >> j - 1)& 0x01) == 1:
                    is_OK = False
                    break

            if src - 1 == dst:
                if dst == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src + 1 == dst:
                if src == j:
                    if ((i >> j) & 0x01) == 1:
                        pass
                    else:
                        is_OK = False
                        break
            elif src == dst:
                if src == j or src - 1 == j:
                    if ((i >> j) & 0x01) == 0 :
                        pass
                    else:
                        is_OK = False
                        break
        if is_OK == True:
            count += 1
    return count


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
##    field1 = [[[] for i in range(W)] for i in range(H)]
##    for i in range(H):
##        for j in range(W):
##            if j + 1 < W and i % 2 == 0:
##                field1[i][j].append((i, j + 1))
##            if j - 1 >= 0 and i % 2 == 1:
##                field1[i][j].append((i, j - 1))
##            if i + 1 < H:
##                field1[i][j].append((i + 1, j))

    dp = [[0 for j in range(W)] for i in range(H + 1)]
    dp[0][0] = 1L
    p = 1000000007L
    for i in range(H):
        for j in range(W):
            dp[i + 1][j] = (dp[i + 1][j] + ((calc_pattern_num(j, j, W) * dp[i][j])) % p) % p
            if j + 1 < W:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + ((calc_pattern_num(j, j + 1, W) * dp[i][j])) % p) % p
            if j - 1 >= 0:
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + ((calc_pattern_num(j, j - 1, W) * dp[i][j])) % p) % p

    print dp[H][K - 1]


##    field2 = [[[] for i in range(W)] for i in range(H)]
##    for i in range(H):
##        for j in range(W):
##            if j + 1 < W and i % 2 == 1:
##                field2[i][j].append((i, j + 1))
##            if j - 1 >= 0 and i % 2 == 0:
##                field2[i][j].append((i, j - 1))
##            if i + 1 < H:
##                field2[i][j].append((i + 1, j))
##
##    dp2 = [[0 for j in range(W)] for i in range(H)]
##    dp2[0][0] = 1
##
##    for i in range(H):
##        for j in range(W):
##            for adj in field2[i][j]:
##                dp2[adj[0]][adj[1]] = (dp2[adj[0]][adj[1]] + dp2[i][j]) % (1000000007)
##
##    print power_func(2, (dp1[H -1][K - 1] + dp2[H -1][K - 1]) , 1000000007) - 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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

    dp = [[0 for j in range(w)] for i in range(h+1)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            for l in range(2**(w-1)):
                for m in range(w-2):
                    if (l >> m) & 1 and (l >> (m+1) & 1):
                        break
                else:
                    if j < w - 1 and (l >> j) & 1:
                        dp[i+1][j+1] += dp[i][j]
                        dp[i+1][j+1] %= MOD
                    elif 0 < j and (l >> (j-1)) & 1:
                        dp[i+1][j-1] += dp[i][j]
                        dp[i+1][j-1] %= MOD
                    else:
                        dp[i+1][j] += dp[i][j]
                        dp[i+1][j] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 平行な縦線がx本あるとき、横線の引き方はfib[x]通り
fib = [1, 1, 2, 3, 5, 8, 13, 21, 34]

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

for h in range(1, H + 1):
    for w in range(1, W + 1):
        dp[h][w] = dp[h - 1][w] * fib[w - 1] * fib[W - w]
        if w > 1:
            dp[h][w] += dp[h - 1][w - 1] * fib[w - 2] * fib[W - w]
        if w < W:
            dp[h][w] += dp[h - 1][w + 1] * fib[w - 1] * fib[W - w - 1]
        dp[h][w] %= mod

print(dp[H][K])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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

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

    cnt, valid = [0] * (w-1), []
    for i in range(2**(w-1)):
        c = [0] * (w-1)
        for j in range(w-1):
            if (i >> j) & 1:
                c[j] = 1

                if 0 < j and c[j-1] == 1:
                    break

        else:
            valid.append(c)
            for j in range(w-1):
                if c[j] == 1:
                    cnt[j] += 1

    num, ans = len(valid), 0
    for v in valid:
        dp = [[0] * w for i in range(h + 1)]
        if v[0]:
            dp[1][1] += 1
        else:
            dp[1][0] += 1

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

        ans = (ans+dp[h][k-1]) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if W == 1:
    print(1)
else:
    def fib(j):
        if j == 0 or j == 1:
            return 1
        else:
            count = 0
            for num in range(2 ** (j - 1)):
                bit = str(bin(num))
                flag = 1
                for i in range(2, len(bit) - 1):
                    if bit[i] == '1' and bit[i + 1] == '1':
                        flag = 0
                count += flag
            return count
    dp = [[1] + [0] * (W - 1)]
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i + 1] * fib(i) * fib(W - i - 2)) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i - 1] * fib(i - 1) * fib(W - i - 1)) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib(i) * fib(W - i - 1) + dp[j - 1][i + 1] * fib(i) * fib(W - i - 2) + dp[j - 1][i - 1] * fib(i - 1) * fib(W - i - 1)) % 1000000007
    print(dp[H][K - 1])

Submission status: Accepted

Solution code:
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
if W == 1:
    print(1)
else:
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
    print(dp[H][K - 1])

Submission status: Accepted

Solution code:
def X_amida_number(W, W_i):
    x_amida = "0" * (W - 1)

    if (W_i-2 >= 0):
        left_x_amida = x_amida[:(W_i-2)]
    else:
        left_x_amida = ""

    right_x_amida = x_amida[(W_i+1):]

    if(len(left_x_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_x_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_x_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_x_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1

    else:
        right_counter = 1

    return (left_counter * right_counter)

def Y_amida_number(W, W_i):
    y_amida = "0" * (W - 1)

    if (W_i-1 >= 0):
        left_y_amida = y_amida[:W_i-1]
    else:
        left_y_amida = ""

    right_y_amida = y_amida[W_i+1:]

    if(len(left_y_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_y_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_y_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_y_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1
    else:
        right_counter = 1

    return (left_counter * right_counter)

def Z_amida_number(W, W_i):
    z_amida = "0" * (W - 1)

    if (W_i-1 >= 0):
        left_z_amida = z_amida[:W_i-1]
    else:
        left_z_amida = ""

    right_z_amida = z_amida[W_i+2:]

    if(len(left_z_amida) > 0):
        left_counter = 0

        for left_bin in range(2**len(left_z_amida)):
            if (("11" in format(left_bin, "b")) == False):
                left_counter += 1
    else:
        left_counter = 1

    if(len(right_z_amida) > 0):
        right_counter = 0

        for right_bin in range(2**len(right_z_amida)):
            if (("11" in format(right_bin, "b")) == False):
                right_counter += 1
    else:
        right_counter = 1

    return (left_counter * right_counter)


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

seed_dp_array = [0 for i in range(W)]
dp_array = [list(seed_dp_array) for i in range(H + 1)]
dp_array[0][0] = 1

for H_i in range(1, H + 1):
    for W_i in range(W):
        if (W_i == 0):
            if(W == 1):
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
            else:
                dp_array[H_i][0] = dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)
        elif (W_i == (W - 1)):
            dp_array[H_i][W - 1] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i)
        else:
            dp_array[H_i][W_i] = dp_array[H_i - 1][W_i - 1] * X_amida_number(W, W_i) + dp_array[H_i - 1][W_i] * Y_amida_number(W, W_i) + dp_array[H_i - 1][W_i + 1] * Z_amida_number(W, W_i)

print(dp_array[H][K - 1] % 1000000007)

Submission status: Accepted

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque

MOD = (10 ** 9) + 7

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

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

L = []

ng_mask = 0b11

for i in range(2 ** (W - 1)):
    isOK = True
    for j in range(W - 1 - 1):
        m = ng_mask << j
        if (i & m) == m:
            isOK = False
    if isOK:
        L.append(i)

# for l in L:
#     print("{:08b}".format(l))


def getBit(n, i):
    i = i - 1
    tmp = n & (1 << i)
    return tmp != 0


dp[0][1] = 1

for h in range(1, H+1):
    for w in range(1, W+1):
        for l in L:
            d = 0
            if w == 1:
                if w == W:
                    d = dp[h - 1][w]
                else:
                    if getBit(l, w) == False:
                        d = dp[h - 1][w]
                    else:
                        d = dp[h - 1][w + 1]
            elif w == W:
                if getBit(l, w - 1):
                    d = dp[h - 1][w - 1]
                else:
                    d = dp[h - 1][w]
            else:
                if getBit(l, w - 1):
                    d = dp[h - 1][w - 1]
                elif getBit(l, w):
                    d = dp[h - 1][w + 1]
                else:
                    d = dp[h - 1][w]
            dp[h][w] += d

print(dp[H][K] % MOD)

sys.exit(0)

Submission status: Accepted

Solution code:
high,wide,end=map(int,input().split())

dp=[[[-1,-1,-1] for _ in range(wide)] for _ in range(high)]
fb=[-1 for _ in range(8)]
fb[0]=1
fb[1]=1
def MakeFibo(i):
    if fb[i-1]==-1:
        fb[i-1]=MakeFibo(i-1)
    if fb[i-2]==-1:
        fb[i-2]=MakeFibo(i-2)
    fb[i]=fb[i-1]+fb[i-2]
    return fb[i]
MakeFibo(7)
#fit 0
wide-=1
high-=1
end-=1
mod=10**9+7
def NZ(x):  #NegativeZero
    if x<0:
        return 0
    else:
        return x


def amida(h,w,f):
    dp[h][w][2]=fb[NZ(w)]*fb[NZ(wide-w)]
    if f == 1: #go straight
        if h==high and w==end:
            dp[h][w][f]=1
        elif h==high:
            dp[h][w][f]=0
        else: #sum under
            if dp[h+1][w][1] == -1:
                amida(h+1,w,1)
            if dp[h+1][w][0] == -1:
                amida(h+1,w,0)
            dp[h][w][f]=dp[h+1][w][0]+dp[h+1][w][1]*dp[h+1][w][2]
    else: #f==0 go side
        dp[h][w][f]=0
        if w-1>=0: #sum left
            if dp[h][w-1][1]==-1:
                amida(h,w-1,1)
            dp[h][w][f]+=dp[h][w-1][1]*fb[NZ(w-1)]*fb[NZ(wide-w)]
        if w+1<=wide: #sum right
            if dp[h][w+1][1]==-1:
                amida(h,w+1,1)
            dp[h][w][f]+=dp[h][w+1][1]*fb[NZ(w)]*fb[NZ(wide-w-1)]
    dp[h][w][f]%=mod

amida(0,0,0)
amida(0,0,1)

print((dp[0][0][0]+dp[0][0][1]*dp[0][0][2])%mod)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
dp = [[0] * w for _ in range(h + 1)]
dp[0][0] = 1
fb = (1, 1, 2, 3, 5, 8, 13, 21)
for y in range(1, h + 1):
    for x in range(w):
        if x - 1 >= 0:
            dp[y][x] += dp[y - 1][x - 1] * fb[x - 1] * fb[w - x - 1]
        if x + 1 <= w - 1:
            dp[y][x] += dp[y - 1][x + 1] * fb[x] * fb[w - x - 2]
        dp[y][x] += dp[y - 1][x] * fb[x] * fb[w - x - 1]
        dp[y][x] %= 1000000007
print(dp[h][k - 1])

Submission status: Accepted

Solution code:
(h, w, k) = list(map(int, input().split()))
n = [0, 1] + [0 for _ in range(w - 1)]
c = {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21}
for i in range(h):
    nn = [0 for _ in range(w + 1)]
    for j in range(1, w + 1):
        nn[j] += c[max(0, j - 1)] * n[j]     * c[max(0, w - j)]
    for j in range(2, w + 1):
        nn[j] += c[max(0, j - 2)] * n[j - 1] * c[max(0, w - j)]
    for j in range(1, w):
        nn[j] += c[max(0, j - 1)] * n[j + 1] * c[max(0, w - j - 1)]
    n = nn

print(n[k] % 1000000007)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())

lis = [0]*(w-1)
n = 0
for i in range(2**(w-1)):
    
    tmp = bin(i)[2:].zfill(w-1)
    if '11' in tmp:continue
    n += 1
    for j in range(w-1):
        lis[j] += int(tmp[j])


res = [1]+[0]*(w-1)
for i in range(h):
    res2 = res.copy()
    for j in range(w):
        if j == 0:
            a=0
            x = 0
        else:
            a = lis[j-1]
            x = res[j-1]
        if j== w-1:
            b = 0
            y = 0
        else:
            b = lis[j]
            y = res[j+1]
        res2[j] = x*a + res[j]*(n - a - b) + y*b
    res = res2
print(res[k-1] % (10**9+7))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    h,w,k = LI()
    t = [1, 1, 2, 3, 5, 8, 13, 21]
    a = [0] * w
    a[0] = 1
    for i in range(h):
        n = [0] * w
        for j in range(w):
            n[j] = a[j] * t[j] * t[w-j-1] % mod
        for j in range(w-1):
            lr = t[j] * t[w-j-2]
            n[j] += a[j+1] * lr % mod
            n[j+1] += a[j] * lr % mod
        a = n

    return a[k-1] % mod


print(main())

Submission status: Accepted

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

fb_dic = {}
def fb(n):
  if n < 0:
    print("error")
    return -1
  if n == 0:
    return 1
  if n == 1:
    return 1
  if n in fb_dic:
    return fb_dic[n]
  ret = fb(n - 1) + fb(n - 2)
  fb_dic[n] = ret
  return ret

for y in range(1, h + 1):
  for x in range(w):
    if x - 1 >= 0:
      dp[y][x] += dp[y - 1][x - 1] * fb(x - 1) * fb(w - x - 1)
    if x + 1 <= w - 1:
      dp[y][x] += dp[y - 1][x + 1] * fb(x) * fb(w - x - 2)
    dp[y][x] += dp[y - 1][x] * fb(x) * fb(w - x - 1)
    dp[y][x] %= 1000000007


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

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:
m = 10**9+7
h, w, k = map(int, input().split())
a = [0]*(w-1) + [1]
for i in range(w-1):
    a[i] = a[i-1] + a[i-2]
dp = [0]*w
tmp = [0]*w
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]
        if i != w-1:
            tmp[i] += dp[i+1]*a[i-1]*a[w-i-3]
        if i != 0:
            tmp[i] += dp[i-1]*a[i-2]*a[w-i-2]
        tmp[i] %= m
    dp, tmp = tmp, dp
print(dp[k-1])

Submission status: Accepted

Solution code:
h, w, k = map(int, raw_input().split())
arr = [1, 2, 3, 5, 8, 13, 21, 34]


def p(num):
    return max(0, num)

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

        if i == 0:
            if j == 0:
                r[i][j] = 1
            else:
                r[i][j] = 0
        else:
            y = r[i - 1][j]
            if j - 1 < 0:
                x = 0
            else:
                x = r[i - 1][j - 1]
            if j + 1 > w - 1:
                z = 0
            else:
                z = r[i - 1][j + 1]
            r[i][j] = (x * arr[p(j-2)] * arr[p(w-j-2)] + \
                y * arr[p(j-1)] * arr[p(w-j-2)] + \
                z * arr[p(j-1)] * arr[p(w-j-3)]) % (10**9+7)
    

print r[h][k-1]

Submission status: Accepted

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

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

#2進数の01で横棒の配置を識別
for b in range(2 ** (W - 1)):
    b = bin(b)[2:].zfill(W - 1)
    #1が連続する場合、横棒のルールに違反するためスキップ
    ok = True
    for i in range(W - 2):
        if b[i] == "1" and b[i + 1] == "1":
            ok = False
    if ok:
        #p:遷移先のindex
        p = list(range(W))
        for i in range(W - 1):
            # 横棒が無い場合、縦棒kから縦棒kに遷移
            # 横棒がある場合、縦棒k-縦棒k+1間を遷移 -> p[i],p[i+1]の入れ替えで表現
            if b[i] == "1":
                p[i], p[i + 1] = p[i + 1], p[i]
        #遷移パターン数をカウント
        for i in range(W):
            transition[i][p[i]] += 1

#DPループ
dp = [[0] * (W + 1) for _ in range(H + 1)]
#初期値:0行目で縦棒1にいるパターン数は1
dp[0][0] = 1
#dpの添え字1のループ
for y in range(H):
    #dpの添え字2のループ
    for i in range(W):
        #下記の式の和を取るループ
        for x in range(W):
            #y+1行目に縦棒iにいるパターン数 = Σx (y行目に縦棒xにいるパターン数 * 縦棒xから縦棒iに移動するパターン数)
            dp[y + 1][i] += dp[y][x] * transition[x][i]
            dp[y + 1][i] %= MOD

#出力
print(dp[H][K - 1])

Submission status: Accepted

Solution code:
# ABC 113 D
MOD = 7 + 10**9 
H, W, K = map(int,input().split())
dp = [[0 for k in range(W)] for l in range(H+1)]

dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1<<(W-1)):
            f = 1
            for l in range(W-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    f = 0
            if f:
                if 0<j and (k>>(j-1))&1:
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j <= W-2 and (k>>j)&1:
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD

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

Submission status: Accepted

Solution code:
import numpy as np

# N:県, M:市
h, w, k = list(map(int, input().split()))

G = np.array([[[0] * w]* w]*h)

# print(G)

# print(G[0,0,:])

# 0番目の行列
def f(i):
  f_list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
  return f_list[i]

for a in range(w):
  # a+1が「何本目」にあたる
  # print(G[0, a, a])
  G[0, a, a] = f(a) * f(w-a-1)
  if a <= w-2:
	  G[0, a, a+1] = f(a) * f(w-a-2)
  if a >= 1:
  	G[0, a, a-1] = f(a-1) * f(w-a-1)

for j in range(1, h):
  for a in range(w):
    for b in range(w):
      G[j, a, b] = G[j-1, a, b] * G[0, b, b]
      if b <= w-2:
        G[j, a, b] += G[j-1, a, b+1] * G[0, b+1, b] 
      if b >= 1:
        G[j, a, b] += G[j-1, a, b-1] * G[0, b-1, b]
      G[j, a, b] = G[j, a, b] % 1000000007


# print(G)

print(G[h-1, 0, k-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    num = [[0] * 9 for _ in range(9)]
    for b in range(2 ** (W - 1)):
        b = bin(b)[2:].zfill(W - 1)
        ok = True
        for i in range(len(b) - 1):
            if b[i] == "1" and b[i + 1] == "1":
                ok = False
        if ok:
            p = list(range(W))
            for i in range(len(b)):
                if b[i] == "1":
                    p[i], p[i + 1] = p[i + 1], p[i]

            for i in range(W):
                num[i][p[i]] += 1

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1
    for y in range(H):
        for x in range(W):
            for i in range(W):
                dp[y + 1][i] += dp[y][x] * num[x][i]
                dp[y + 1][i] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10**9 + 7

def cpst(s, n):
    a = '0' * (n-len(s))
    return a + s

def makeb(n):
    l = []
    for i in range(2**n):
        tmp = bin(i)[2:]
        l.append(cpst(tmp, n))
    return l

tmp_bits = makeb(w-1)
bits = []
for x in tmp_bits:
    flag = True
    for i in range(w-2):
        if x[i] == '1' and x[i+1] == '1':
            flag = False
            break
    if flag:
        bits.append(x)

table = [[0,0,0] for _ in range(w)]

for x in bits:
    for i,y in enumerate(x):
        if y == '1':
            table[i][2] += 1
            table[i+1][0] += 1
        else:
            if i == 0:
                table[0][1] += 1
            else:
                if x[i-1] == '0':
                    table[i][1] += 1
            if i == w-2:
                table[w-1][1] += 1

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

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

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