好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：SGU 223

在 $n \times n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子（即上下左右和四个对角方向），求使它们无法互相攻击的方案总数。

---

输入格式

只有一行，包含两个整数 $n$ 和 $k$。

---

输出格式

输出一行，为方案总数，若不能够放置则输出 $0$。

---

样例

样例输入 1

3 2

样例输出 1

16

样例解释 1

$n=3$，棋盘 $3\times 3$，放置 $k=2$ 个国王，要求国王之间不能攻击。

我们可以枚举所有放置方案，计算总数为 $16$。

具体验证：对于 $3\times 3$ 棋盘，放置两个国王且不相互攻击的方案共 $16$ 种（可通过搜索或状态压缩 DP 计算得到）。

---

样例输入 2

4 4

样例输出 2

79

---

数据范围

对于全部数据：

• $1 \le n \le 10$
• $0 \le k \le n^2$

---

时空限制

• 时间：$500 \text{ ms}$
• 内存：$65536 \text{ KB}$（注意此题内存限制较小，为 64 MB）

---

提示
此题为 状态压缩 DP（状压 DP）经典题。

状态设计：

• 用二进制数表示一行的国王放置情况：$1$ 表示放国王，$0$ 表示不放；
• 状态必须满足：一行内不能有相邻的国王（即二进制数中不能有两个连续的 $1$）；
• 相邻两行之间，上一行的状态 $s1$ 和下一行的状态 $s2$ 必须满足：
  1. $s1$ 和 $s2$ 不能在同一列有国王（即 $s1 \& s2 = 0$）；
  2. $s1$ 和 $s2$ 的国王不能在相邻列（即 $(s1 \ll 1) \& s2 = 0$ 且 $(s1 \gg 1) \& s2 = 0$）。

设 $dp[i][j][s]$ 表示前 $i$ 行，已经放置了 $j$ 个国王，且第 $i$ 行的状态为 $s$ 的方案数。

转移方程：

$$dp[i][j][s] = \sum_{s'} dp[i-1][j - \text{popcount}(s)][s']$$

其中 $s'$ 是第 $i-1$ 行的状态，且 $s$ 和 $s'$ 满足上述条件。

初始化：$dp[0][0][0] = 1$。

最终答案：

$$\text{ans} = \sum_{s} dp[n][k][s]$$

优化：

• 预处理所有合法行状态（一行内不相邻）及该状态的国王数 $\text{popcount}(s)$；
• 预处理状态间的兼容性（两行不攻击）。

复杂度：$O(n \times k \times |S|^2)$，其中 $|S|$ 是合法行状态数，对于 $n \le 10$，$|S| \le 144$，可以接受。