Topic Links
Place (N\times N\) kings on the board so that they don't attack each other. How many kinds of placing schemes are there? The king can attack it up and down, left, left, left, right, right and down eight directions near each lattice, a total of (8\\\\\\\.
\(1\le N\le 9,0\le K\le N*N\)
\ (f(i,j,l) denotes the preceding (i) line, the current state is (j), and the scheme of (l) King's time has been placed.
\ (j) This dimension is expressed in binary
Preprocess all legitimate states on a row (excluding two adjacent states on the same row), and then enumerate them directly to match the state of the previous row.
\(f(i,j,l) = \sum f(i-1,x,l-num(x))\)
\ (num(x)) How many 1 is x in binary system?
When transferring, it is necessary to rule out the illegitimacy of the king's attack on each other between the two lines.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> sta,stan;
ll d[10][(1<<10)][100];
int n,k;
bool ok(int i,int j){
    if(i & j)return false;
    if((i << 1) & j)return false;
    if(i & (j << 1))return false;
    return true;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<(1<<n);i++){
        int num = 0;
        bool flag = true;
        for(int j=0;j<n-1;j++){
            if(i >> j & 1){
                num++;
                if(i >> (j+1) & 1){
                    flag = false;
                    break;
                }
            }
        }
        if(!flag)continue;
        sta.push_back(i);
        stan.push_back(num + (i >> (n-1) & 1));
    }
    for(int i=0;i<sta.size();i++){
        d[1][i][stan[i]] = 1;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<sta.size();j++){
            for(int t=0;t<sta.size();t++){
                if(ok(sta[j],sta[t])){
                    for(int p = stan[j];p <= k;p++){
                        d[i][j][p] += d[i-1][t][p-stan[j]];
                    }
                }
            }
        }
    }
    ll res = 0;
    for(int i=0;i<sta.size();i++)
        res += d[n][i][k];
    cout<<res<<endl;
    return 0;
}