Luogu p1896 non aggression

Title Description

Topic link
stay N×N In my chessboard K A king , Keep them from attacking each other , How many layout plans are there . The king can attack it up, down, left and right , And a grid in the upper left, lower left, upper right and lower right directions , common 8 Lattice .

Input format

There is only one line , It contains two numbers N,K （ 1 <=N <=9, 0 <= K <= N * N）

Output format

The number of schemes obtained

#include<bits/stdc++.h>
using namespace std;
int sat[2000], siz[2000];//sat  Legal status of a line  siz How many kings are there in the current state  
int cnt = 0;
int n, m;
long long f[10][2000][100] = {
     0 };//f[i][j][k] The first i That's ok   Status as j  discharge k Number of King's schemes 
void dfs(int Sta, int now_size, int i_th)// Preprocess each state  Sta  Represents the state  00000 now_size Represents how many kings there are now  i_th Represents which column of grid is currently in use 
{
    
    if (i_th >= n)// If it's done （ Note that it is greater than or equal to ）
    {
    
        sat[++cnt] = Sta;// To deal with the first cnt Status 
        siz[cnt] = now_size;// The first cnt The number of kings that can be put in a state is  now_size individual 
        return;// Create a new status 
    }
    dfs(Sta, now_size, i_th + 1);// No, No i_th Lattice 
    dfs(Sta + (1 << i_th), now_size + 1, i_th + 2);// Use the first i_th Lattice , here i_th To add 2, That is to skip the next grid   Because left and right cannot be adjacent 
}
int main()
{
    
    scanf("%d%d", &n, &m);
    dfs(0, 0, 0);
    for (int i = 1; i <= cnt; i++)f[1][i][siz[i]] = 1;// All States of the first layer are 1 In one case 
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= cnt; j++)// The status of the upper layer is j
            for (int k = 1; k <= cnt; k++)// The status of the current layer is k
            {
    
                if (sat[j] & sat[k])continue;// Up and down 
                if ((sat[j] << 1) & sat[k])continue;// Adjacent to the top right 
                if (sat[j] & (sat[k] << 1))continue;// Upper left adjacent 
                for (int s = m; s >= siz[j]; s--)f[i][j][s] += f[i - 1][k][s - siz[j]];// enumeration s, Calculation f[i][j][s]
            }
    long long ans = 0;
    for (int i = 1; i <= cnt; i++)ans += f[n][i][m];// Count the final answer , Remember to use long long
    printf("%lld", ans);
    return 0;
}