简单状态压缩。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(1<<10),M=10;
vector<int>state;
LL f[M][N][M*M],cnt[N],ans=0;
int main(){
	int n,K;scanf("%d%d",&n,&K);
	for(int i=0;i<(1<<n);i++){
		if((i&(i<<1))||(i&(i>>1)))
			continue;
		state.push_back(i);
	}
	for(int i:state){
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				cnt[i]++;
			}
		}
	}
	f[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=K;j++){
			for(int u:state){
				if(cnt[u]>j)continue;
				for(int v:state){
					if(cnt[u]+cnt[v]>j)continue;
					if((u&v)||(u&(v<<1))||(u&(v>>1)))
						continue;
					f[i][u][j]+=f[i-1][v][j-cnt[u]];
				}
			}
		}
	}
	for(int i:state){
		ans=ans+f[n][i][K];
	}
	printf("%lld",ans);
	return 0;
}