pypy3 解法, 执行用时: 169ms, 内存消耗: 25940K, 提交时间: 2023-05-27 19:25:59

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


def check(x, y):
    if x & y or x & x << 1 or x & y << 1 or y & y << 1 or y & x << 1:
        return False
    return True


dp = [[0] * ((1 << n) + 1) for _ in range(k+1)]
dp[0][0] = 1
c = [0] * (1 << n)
for i in range(1, cnt):
    c[i] = c[i >> 1] + (1 & i)

for i in range(n):
    dp0 = [[0] * ((1 << n) + 1) for _ in range(k+1)]
    # dp0[0][0] = 1
    for j in range(cnt + 1):
        for t in range(cnt + 1):
            if check(j, t):
                for p in range(c[j] + c[t], k + 1):
                    dp0[p][j] += dp[p - c[j]][t]
    dp = dp0
print(sum(dp[k]))

C++ 解法, 执行用时: 7ms, 内存消耗: 1792K, 提交时间: 2022-07-06 14:06:25

#include<bits/stdc++.h>
long long n,K,ans=0,dp[100][2020][100];
int main(){
    std::cin>>n>>K;
    for(int i=0;i<(1<<n);i++) if(!(i&(i<<1LL))) dp[1][i][__builtin_popcount(i)]=1;
    for(int i=2;i<=n+1;i++) for(int j=0;j<(1<<n);j++) for(int k=0;k<(1<<n);k++) if(!(j&(j<<1LL))&&!(k&(k<<1LL))&&!(k&j)&&!(j&(k<<1LL))&&!(k&(j<<1LL))) for(int num=0;num+__builtin_popcount(j)<=K;num++) dp[i][j][num+__builtin_popcount(j)]+=dp[i-1][k][num];
    std::cout<<dp[n+1][0][K]<<'\n';
    return 0;
}