[acwing 1064 little king] shaped pressure DP

Topic link

The question

You need to be in a n*n Put your chessboard k A chess piece , Make them not attack each other , Every king will treat his neighbor 8 Location attack , Now, how many placement schemes do you have

Ideas

The amount of data is 10, Obvious pressure dp topic ,f[i][j][k] It represents the front i-1 That's ok , Now the first i The row status is j, The total number of pieces is k Number of alternatives , We can preprocess every legal state in advance , And every state that can be transferred can also be preprocessed , Then there is the pressure dp Part of , There is one thing to note , It is to judge the left shift and right shift during state transition preprocessing , Originally, I wrote only shift left , It is found that the answer is larger than the standard answer , The state that can be transferred during pretreatment increases , Therefore, it is correct to add a shift right judgment , Now look at the code ：

#include<bits/stdc++.h>
using namespace std;
const int N = 12;
vector<long long> hefa;
vector<long long> zhuanyi[1<<N];
long long f[N][1<<N][N*N],cnt[1<<N];
int count(int x){
    
	int ans = 0;
	while(x) ans += (x&1),x >>= 1;
	return ans;
}
int main(){
    
	int n,k;	
	cin>>n>>k;
	zhuanyi[0].push_back(0);
	for(int i=0;i<(1<<n);i++){
    
		if((i&(i>>1)) == 0) hefa.push_back(i);
		cnt[i] = count(i);
	}
	f[0][0][0] = 1;
	for(int i=0;i<hefa.size();i++){
    
		for(int j=i+1;j<hefa.size();j++){
    
			long long x = hefa[i],y = hefa[j];
			if(((x>>1)&(y)) == 0 && (x&y) == 0 && (x&(y>>1)) == 0) zhuanyi[x].push_back(y),zhuanyi[y].push_back(x);
			// This is the place , Judge at the same time (x>>1)&(y) == 0 and (x&(y>>1)) == 0, Or you'll make a mistake 
		}
	}
// for(int i=0;i<hefa.size();i++){
    
// cout<<hefa[i]<<' ';
// for(auto t : zhuanyi[hefa[i]]) cout<<t<<' ';
// cout<<endl;
// }
	long long ans = 0;
	for(int i=1;i<=n;i++){
    
		for(int s=0;s<=k;s++)
			for(auto x : hefa){
    
				for(auto y : zhuanyi[x]){
    
					if(s >= cnt[x])
					f[i][x][s] += f[i-1][y][s-cnt[x]];
				}
			}
	}
	for(auto t : hefa) ans += f[n][t][k];
	cout<<ans<<endl;
	return 0;
}