rt，附代码

#include<iostream>
using namespace std;
int n,k;
long long f[9][1<<9][81],ans;
int c(int st){
	int cnt=0;
	while(st!=0){
		if(st%2){
			cnt++;
		}
		cnt/=2;
	}
	return cnt;
}
bool check1(int st){
	for(int i=0;i+1<n;i++){
		if((st&(1<<i))&&(st&(1<<(i+1)))){
			return false;
		}
	}
	return true;
}
bool check2(int st,int st2){
	for(int i=0;i<n;i++){
		if(st&(1<<i)){
			if(st2&(1<<i)){
				return false;
			}
			else if(i+1<n&&(st2&(1<<(i-1)))){
				return false;
			}
			else if(i-1>0&&(st2&(1<<(i-1)))){
				return false;
			}
		}
	}
	return true;
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		for(int st=0;st<(1<<n);st++){
			if(!check1(st)){
				continue;
			}
			if(i==0){
				f[i][st][c(st)]=1;
			}
			else{
				for(int j=c(st);j<=k;j++){
					for(int st2=0;st2<(1<<n);st2++){
						if(!check1(st2)||!check2(st,st2)){
							continue;
						}
						f[i][st][j]+=f[i-1][st2][j-c(st)];
					}
				}
			}
		}
	}
	for(int st=0;st<(1<<n);st++){
		ans+=f[n-1][st][k];
	}
	cout<<ans;
}