```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 2005
int n,k,s,tot,num,s1,s2;
int ok[N],cnt[N],dp[10][N][N];
signed main(){
cin>>n>>k;
for(int i=0;i<(1<<n);i++){
s=i,tot=0;
if(((s<<1)&s==0)&&((s>>1)&s==0))
{
ok[++num]=s;
while(s){
if(s&1)++tot;
s>>=1;
}
cnt[i]=tot;
}
}
cout<<num<<endl;
for(int i=1;i<=num;i++){
cout<<ok[i]<<" "<<cnt[ok[i]]<<endl;
}
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=num;j++){
//此行
s1=ok[j];
for(int l=1;l<=num;l++){
//上行
s2=ok[l];
if(s2<<1&s1==0&&s2>>1&s1==0&&s2&s1==0){
for(int h=cnt[s1];h<=k;h++){
dp[i][h][s1]+=dp[i-1][h-cnt[s1]][s2];
}
}
}
}
}
int ans=0;
for(int i=1;i<=num;i++){
ans+=dp[n][k][ok[i]];
}
cout<<ans;
return 0;
}
```
cnt[i]=tot;
结果同上
by MD_silverbullet @ 2023-10-02 16:32:35
警钟长鸣（）
拜谢@[AC_love](https://www.luogu.com.cn/user/186472)大佬 @[Sarah_zhang](https://www.luogu.com.cn/user/561157)大佬
此贴结
by MD_silverbullet @ 2023-10-03 12:47:22