题目
#include<cstdio> #include<algorithm> #define low(i) (i)&(-i) using namespace std; typedef long long ll; const int N=9+1,M=(1<<N); int A[M],num[M],tot;ll dp[N][M][82]; inline int get_one(int x){ int num=0; while(x) ++num,x-=low(x); return num; } inline int isok(int x,int y) {return !((x&y)||(x&(y>>1))||(x&(y<<1)));} int main(){ int n,K,t;scanf("%d%d",&n,&K),t=(1<<n); for(int i=0;i<t;++i){ if(!(i&(i>>1))&&!(i&(i<<1))){ int d=get_one(i); if(d>K) continue; A[++tot]=i,num[tot]=d; } } for(int j=1;j<=tot;++j) dp[1][j][num[j]]=1; for(int i=2;i<=n;++i) for(int j=1;j<=tot;++j) for(int k=1;k<=tot;++k) if(isok(A[j],A[k])) for(int o=num[j];o<=K;++o) dp[i][j][o]+=dp[i-1][k][o-num[j]]; ll ans=0; for(int j=1;j<=tot;++j) ans+=dp[n][j][K]; printf("%lld\n",ans); }