题意：
在 $ N×N $ 的棋盘里面放 $ K $ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $ 8 $ 个格子。
数据范围： $ 1 \le N \le 9,0 \le K \le N * N $
题解：
算法：状压dp
使用 $stt[]$ 记录每一种状态，二进制下从低位到高位记录此行从左到右是否放置国王。
并且由于有数量限制，使用 $sum[]$ 记录该种状态使用的国王数。
考虑状态转移方程，预处理出每一种状态 $stt[]$ 及其使用的国王数 $sum[]$ ，用 $dp[i][j][s]$ 表示考虑前 $i$ 行且第 $i$ 行状态编号为 $j$ ，前 $i$ 行共使用 $s$ 个国王时的方案数。可以得出：
$$dp[i][j][s]= \sum dp[i-1][k][s-sum[j]]$$
其中 $j$ 与 $k$ 对应的状态需满足题目条件，即不能为以下几种情况：
sum[j]&sum[k]（上/下）
(sum[j]<<1)&sum[k]（左上/右下）
sum[j]&(sum[k]<<1)（右上/左下）
此外，注意开 $long\ long$。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int N=15;
int n,m;
int tot,cnt;
LL ans;
int sum[1<<N],stt[1<<N];
LL dp[N][1<<N][N*N];
inline int calc(int x){
int res=0;
for(;x;x&=x-1)
res++;
return sum[cnt]=res;
}
int main(){
scanf("%d%d",&n,&m);
tot=(1<<n)-1;
for(int i=0;i<=tot;i++)
if(!(i&(i<<1))){
stt[++cnt]=i;
dp[1][cnt][calc(i)]=1;
}
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++){
int x=stt[j];
for(int k=1;k<=cnt;k++){
int y=stt[k];
if((x&y) || (x&(y<<1)) || ((x<<1)&y))
continue;
for(int l=0;l<=m;l++)
dp[i][j][sum[j]+l]+=dp[i-1][k][l];
}
}
for(int i=1;i<=cnt;i++)
ans+=dp[n][i][m];
printf("%lld",ans);
return 0;
}