棋盘式状压dp
cpp
int cnt[1<<M];//当前状态行1的个数
vector<int> state;//存储可选行
int dp[2][M*M][1<<M];//dp[i][j][k]表示第i行选了j个国王当前状态为k的方案数
int n,m;
vector<int> head[1<<M];//可以与相应行匹配的其他行
bool check(int x){//判断可选行
for(int i=0;i<n;i++){
if((x>>i&1)&&(x>>i+1&1))return false;
}
return true;
}
int count(int x){
int res=0;
for(int i=0;i<n;i++)res+=(x>>i&1);
return res;
}
void solve(){
cin>>n>>m;
for(int i=0;i<1<<n;i++){
if(check(i)){
state.push_back(i);
cnt[i]=count(i);
}
}
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
int a=state[i],b=state[j];
if((a&b)==0&&check(a|b))head[i].push_back(j);
}
}
dp[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=m;j>=0;j--){
for(int a=0;a<state.size();a++){
for(int b:head[a]){
int c=cnt[state[a]];
if(j>=c)dp[i&1][j][a]+=dp[i-1&1][j-c][b];
}
}
}
memset(dp[i-1&1],0,sizeof(dp[i-1&1]));
}
cout<<dp[n+1&1][m][0];
}