国际象棋
众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。
已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。
由于方案数可能很大，只需计算答案除以 $1000000007$ (即 ${10}^{9}+7$) 的余数。
如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 $(x,y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(x+1,y+2)$、$(x+1,y−2)$、$(x−1,y+2)$、$(x−1,y−2)$、$(x+2,y+1)$、$(x+2,y−1)$、$(x−2,y+1)$ 和 $(x−2,y−1)$ 共 $8$ 个格子。
输入格式
输入一行包含三个正整数 $N,M,K$，分别表示棋盘的行数、列数和马的个数。
输出格式
输出一个整数，表示摆放的方案数除以 $1000000007$ (即 ${10}^{9}+7$) 的余数。
数据范围
对于 $5\%$ 的评测用例，$K=1$；
对于另外 $10\%$ 的评测用例，$K=2$；
对于另外 $10\%$ 的评测用例，$N=1$；
对于另外 $20\%$ 的评测用例，$N,M \leq 6$，$K \leq 5$；
对于另外 $25\%$ 的评测用例，$N \leq 3$，$M \leq 20$，$K \leq 12$；
对于所有评测用例，$1 \leq N \leq 6$，$1 \leq M \leq 100$，$1 \leq K \leq 20$。
输入样例1：
1 2 1
输出样例1：
1
输入样例2：
4 4 3
输出样例2：
276
输入样例3：
3 20 12
输出样例3：
914051446
解题思路
可以发现棋盘的行数很小，最大只有$6$，意味着可以用状压dp。现在我们把棋盘旋转$90$度，那么就会变成最多只有$6$列，对于每一行就可以进行状态压缩。
定义状态$f(i,j,u,v)$表示所有摆放完前$i$行，且前$i$行共摆放了$j$个棋子，且第$i$行的状态为$u$，第$i-1$行的状态为$v$的合法方案的集合，属性就是合法方案的数量。为什么状态表示需要两行的状态？这是因为要摆放第$i$行时，不仅需要考虑第$i-1$行的摆放状态，还需要考虑第$i-2$行的摆放状态。因此在状态表示中仅考虑第$i$行的状态时不够的，还需要加多一维来表示第$i-1$行的状态，这样在转移的时候就可以枚举到第$i-2$行了。
假设棋盘（旋转后）有$m$列，那么我们用$m$个二进制位来表示某一行$i$摆放棋子的状态，如果第$k$位为$1$表示在第$i$行第$k$列摆放了棋子。
根据国际象棋的规则，对于相邻的两行$i$和$i-1$，如果在$(i,j)$处摆放了棋子，那么在$(i-1,j-2)$和$(i-1,j+2)$处不能摆放棋子，否则就会相互攻击。因此如果第$i$行的状态为$u$，第$i+1$行的状态为$v$，那么应该要满足$u \ll 2 \mathrm{\ \& \ } v \mathrm{ \ == \ } 0$并且$u \gg 2 \mathrm{\ \& \ } v \mathrm{ \ == \ } 0$。对于第$i$行与$i-2$行，如果在$(i,j)$处摆放了棋子，那么在$(i-1,j-1)$和$(i-1,j+1)$处不能摆放棋子，假设第$i-2$行的状态为$w$，那么应该要满足$u \ll 1 \mathrm{\ \& \ } w \mathrm{ \ == \ } 0$并且$u \gg 1 \mathrm{\ \& \ } w \mathrm{ \ == \ } 0$。
因此状态转移方程就是$$f(i,j,u,v) = \sum{f(i-1,j-c_u,v,w)}$$
其中$c_u$表示$u$在二进制下是$1$的位数。同时$u$与$v$，$u$与$w$，以及$v$与$w$要满足上面所说到的条件。
AC代码如下，时间复杂度为$O(n \times k \times 2^{3m})$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 110, M = 1 << 6, K = 30, mod = 1e9 + 7;
5
6 int f[N][K][M][M];
7 int cnt[M];
8
9 int main() {
10 int n, m, k;
11 cin >> m >> n >> k;
12 for (int i = 0; i < 1 << m; i++) {
13 int t = i;
14 while (t) {
15 cnt[i] += t & 1;
16 t >>= 1;
17 }
18 }
19 f[0][0][0][0] = 1;
20 for (int i = 1; i <= n + 2; i++) {
21 for (int j = 0; j <= k; j++) {
22 for (int u = 0; u < 1 << m; u++) {
23 for (int v = 0; v < 1 << m; v++) {
24 if (!(u << 2 & v) && !(u >> 2 & v) && cnt[u] <= j) {
25 for (int w = 0; w < 1 << m; w++) {
26 if (!(u << 1 & w) && !(u >> 1 & w) && !(v << 2 & w) && !(v >> 2 & w)) {
27 f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j - cnt[u]][v][w]) % mod;
28 }
29 }
30 }
31 }
32 }
33 }
34 }
35 cout << f[n + 2][k][0][0];
36
37 return 0;
38 }
这里枚举到第$n+2$行，其中第$n+1$行与$n+2$行的状态均为$0$等价于所有在前$i$行摆放了$j$个棋子的合法状态。
参考资料
AcWing 3494. 国际象棋（杂题选讲）：https://www.acwing.com/video/2938/
标签：状态,国际象棋,摆放,leq,棋子,mathrm From： https://www.cnblogs.com/onlyblues/p/17290712.html