#include <iostream>
#include <cstdio>
using namespace std;
int n,k,S,f[10][90][600];
int cnt[1000];
long long ans;
inline void init(){
	for(int S=1;S<=(1<<n);S++)
		cnt[S]=__builtin_popcount(S);
}
inline bool check(int S, int T){
	if((S<<1)&T)return false;
	if((T<<1)&S)return false;
	if(S&T)return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&k);
	init();
	f[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=k;j++){  // 枚举当前使用国王的个数 
			for(int S=0;S<(1<<n);S++){  // 枚举当前航状态
			// 当前行在上一行时已经被算出，可以确保已计算 
				if(S&(S>>1)) continue;
				for(int T=0;T<(1<<n);T++){  // 枚举下一行状态 
					if(T&(T>>1))continue;
					if(check(S,T))
						f[i+1][j+cnt[T]][T]+=f[i][j][S];
						// 下一行状态为 T 时，加上当前行状态为 S 的数  
				}
			}
		}
	}
	for(int S=0;S<(1<<n);S++)
		ans+=f[n][k][S];
	printf("%lld",ans);
	return 0;
}

评测链接

WA两个点

这是之前写的代码，现在看不懂了

主要问题在于30行 $j$ 的更新，为什么可以直接使用 $j+cnt[T]$

还有为什么神奇地WA两个点