状压dp（模板）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1030;
int n,m,k,cnt;
int st[N],num[N];
void dfs(int w,int s,int step){
	if(step>=n){
		st[++cnt]=w;
		num[cnt]=s;
		return ;
	}
	dfs(w,s,step+1);
	dfs(w+(1<<step),s+1,step+2);
}
ll f[12][N][90];
int main(){
	cin >> n >> m;
	dfs(0,0,0);
	for(int i=1;i<=cnt;++i) f[1][i][num[i]]=1;
	for(int i=2;i<=n;++i){
		for(int j=1;j<=cnt;++j){
			for(int k=1;k<=cnt;++k){
				if(st[j]&st[k]) continue;
				if((st[j]>>1)&st[k]) continue;
				if((st[j]<<1)&st[k]) continue;
				for(int s=num[j];s<=m;++s) f[i][j][s]+=f[i-1][k][s-num[j]];
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=cnt;++i) ans+=f[n][i][m];
	cout << ans;
	return 0;
}