#include <iostream>
#include <cmath>
#include <cstring>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
long long dp[15][N][110],ans;
int n,m,cnt;
int a[N],sum[N]; 
int main(){
	cin >> n >> m;
	for(int i=0; i<(1<<n); i++)
	{
		if(i & (i << 1) || i & (i >> 1))continue;
		a[++cnt] = i;
		int x = i;
		while(x)
		{
			sum[cnt] += x & 1;
			x >>= 1;
		}
	}
	for(int i = 1;i <= cnt; i++)
	    dp[1][i][sum[i]]=1; 
	for(int i = 2;i <= n; i++)
	{
		for(int j = 1;j <= cnt;j++)
		{
			for(int k = 1;k <= cnt;k++)
			{
				if(a[j]&a[k]||(a[j]>>1)&a[k]||(a[j]<<1)&a[k])continue;
				for(int l=sum[j]+sum[k];l<=m; l++)
				    dp[i][j][l] += dp[i-1][k][l-sum[j]];
			}
		} 
	}
	for(int i=1; i<=cnt; i++)
	    ans += dp[n][i][m];
	cout << ans;
	return 0;
} 

状态压缩动规

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#define int long long
using namespace std;
const int N=(1<<11);
const int INF=0x3f3f3f3f;
int dp[12][N][100],check[N];
int n,m;
void init(){
	for(int i=0;i<(1<<n);i++){
		int x=i;
		while(x>0){
			check[i]++;
			x-=x&(-x);
		}
	}
}
signed main(){
	cin >> n >> m;
	init();
	for(int i=0;i<(1<<n);i++){
		dp[1][i][check[i]]=1;
	}
	for(int le=2;le<=n;le++){
		for(int i=0;i<(1<<n);i++){
			if(i&(i<<1))continue;
			for(int j=0;j<(1<<n);j++){
				if((j&(j<<1))||(i&j)||(i&(j<<1))||(i&(j>>1)))continue;
				for(int k=check[i];k<=m;k++){
					dp[le][i][k]+=dp[le-1][j][k-check[i]];
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		ans+=dp[n][i][m];
	}
	cout << ans;
	return 0;
}