RT

状压+记忆化搜索，学校数据70，洛谷100

9 13以上的数据就能卡掉

建议再次加强

#include <bits/stdc++.h>
using namespace std;
long long a,b,x,ans;
vector<pair<long long,long long> >ik;
bool ik2[103][103];
long long jy[100][11][100];
int dfs(int y,int d,int l)
{
//	cout<<y<<" "<<d<<" "<<l<<endl;
	if(d==a&&y==b)
	{
//		cout<<"000000:"<<endl;
		ans++;
		return 1;
	}
	else if(jy[y][d][l])
	{
		ans+=jy[y][d][l];
		return jy[y][d][l];
	}
	if(d>=a||y>b)
	return 0;
	long long cnt=0;
	for(int i=0;i<ik.size();i++)
	{
		if(ik2[l][i])
		cnt+=dfs(y+ik[i].second,d+1,i);
	}
	jy[y][d][l]=cnt;
	return cnt;
}
int main()
{
//	freopen("1087.in","r",stdin);
//	freopen("1087.out","w",stdout);
	cin>>a>>b;
//	if(b>13&&a==9)
//	return 0; 
	for(int i=0;i<(1<<a);i++)
	{
		if(!((i&(i<<1))||(i&(i>>1))))
		{
			x=i;
			ik.push_back(make_pair(i,0));
			while(x)
			{
				ik[ik.size()-1].second+=x%2;
				x/=2;
			}
		}
	}
	for(int i=0;i<ik.size();i++)
	{
		for(int j=0;j<ik.size();j++)
		{
			int u=ik[i].first;
			int v=ik[j].first;
			if(!((u&v)||(u&(v<<1))||(u&(v>>1))))
			ik2[i][j]=1;
		}
	}
	dfs(0,0,0);
	cout<<ans<<endl;
	return 0;
}