Python 代码

n, k = map(int, input().split())
N = 1 << n

status, cnt = [], [0] * N
dp = [[[0] * N for _ in range(k+1)] for _ in range(n+2)]

def check(st):
    global n
    for i in range(n-1):
        if st >> i & 1 and st >> i + 1 & 1: return False
    return True

def count(st):
    global n
    res = 0
    for i in range(n):
        if st >> i & 1: res += 1
    return res

# 遍历所有状态，筛选出合法状态
for i in range(N):
    if check(i):
        status.append(i)
        cnt[i] = count(i)

st_len = len(status)

ne = [[] for _ in range(N)]

# 找出所有可以相邻的状态对，并进行存储
for i in range(st_len):
    for j in range(i, st_len):
        if (status[i] & status[j]) == 0 and check(status[i] | status[j]):
            ne[status[i]].append(status[j])
            if i != j: ne[status[j]].append(status[i])


dp[0][0][0] = 1
for i in range(1, n+2):
    for cur_num in range(k+1):
        for st1 in status:
            for st2 in ne[st1]:
                if cur_num - cnt[st1]  >= 0:
                    dp[i][cur_num][st1] += dp[i-1][cur_num-cnt[st1]][st2]

print(dp[n+1][k][0])