什么是状压DP
状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。
——OI Wiki
状态压缩
例如，给定一个 bool 数组 $c$，那么 $c_i$ 为 $0$ 或 $1$。
我们可以将其压缩为一个二进制整数 $(a)_2$，这样 a&(1<<i) 即 $c_i$。可以参照下表：
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| $c_i$ | $0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ |
a&(1<<i) |
$0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ |
此时，$(a)_2=(10011010)_2,a=154$。
状压DP
在此基础上进行DP，状态的转移化为了整数，那么状态转移同样得到了优化（位运算）。
设计状态压缩
首先，这是一个 $N\times N$ 的棋盘。
那么，我们考虑压缩一行为一个整数。（当然，压缩列同样可行，你只需要“将棋盘转 $90^\circ$”）
$0$ 表示并没有放置国王，$1$ 表示放置了国王。那么比如 $74=(01001010)_2$ 表示的便是这样的一行：
考虑状态转移
我们定义 $dp[i][j][k]$ 表示：
- DP至第 $i$ 行；
- 共放置了 $j$ 个国王（由于题目给出“放置 $K$ 个国王”）；
- 第 $i$ 行状态为 $k$（因为国王会影响到下一行的状态）。
一个很明显的结论是国王周围 $8$ 个格子内不能有其他国王（如图）。
蓝色为国王，红色为不能走区域（橙色为红色重合部分），绿色为其他国王可以放置的位置。
行内预处理
我们可以先处理行内不可能存在的情况：行内国王相邻。
也就是说，状态 $S$ 内不能存在两个二进制位 $1$ 相邻。
那么我们便可以通过 (S<<1)|S 判断（假设 $S=(110101)_2$）：
S |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
|---|---|---|---|---|---|---|---|
S<<1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 |
不难发现，如果此时有 $1$ 在同一列，那么 $S$ 便会有相邻的 $1$。
事实上，使用 (S>>1)|S 也是可行的，但这不重要。因为两个相邻的 $1$，无论左移还是右移，都是从至少两位 $1$ 重合变为至少一位 $1$ 重合。
所以，当一个状态 $S$ 满足 (((S<<1)|S)&1)==0 时，这一行才可能成立，其余情况可以直接忽略。
于是，开一个 $ok$ 数组记录，$ok[i]$ 表示第 $i$ 大的合法行。
其实还需要预处理一个 $cnt[S]$ ，具体后文会提到。
行间转移
处理完了行内，现在开始处理行间状态转移。
如果第 $i-1$ 行第 $j$ 号位置有一个国王，那么第 $i$ 行第 $j-1,j,j+1$ 号位置都不能有国王。
不妨令第 $i$ 行状态为 $S1$，第 $i-1$ 行为 $S2$。
同样的，由于我们进行了状态压缩，也就是当状态满足 ((S2<<1)&S1)==0&&(S2&S1)==0&&((S2>>1)&S1)==0 时，第 $i$ 行才有可能为状态 $S1$。
对条件进行简写：(((S2<<1)|S2|(S2>>1))&S1)==0。
转移方程至此也就很好理解了：
\[dp[i][j][S1]=\sum_{j=cnt[S1]}^k{dp[i-1][j-cnt[S1]][S2]}\]其中，$cnt[S1]$ 表示二进制整数 $S1$ 中 $1$ 的个数，已经预处理过。
DP边界
\[dp[0][0][0]=1\]很好理解，就是第 (0) 行无法处理，只能放置 $0$ 个国王，第 $-1$ 行无法放置国王。
但是，事实上多数情况都是为了运算方便而如此设计的。
统计答案
首先 $dp$ 数组的前两维很好判断，就是 $n,k$。那么第三维，第 $n$ 行的状态我们是不知道的。事实上为了统计所有可能数，第 $n$ 行什么状态都有可能，因此我们一个一个枚举累加即可。
注意事项
-
开
long long！开long long！开long long！重要的事情说三遍。
-
数组大小
$dp$ 需要开到 $dp[N+1][K+1][2^{N+1}]$。
其中 $N,K$ 需要取最大值 $N=9,K=N^2=81$。（$2^N$ 使用
1<<N，而不是pow(2,N)）$ok,cnt$ 都需要开到 $2^{N+1}$。
考虑到数据范围 $N\leq9$，并不会 $\text{MLE}$。
-
运算优先级
参见OI Wiki，可以发现
&、^、|这三个位运算符的优先级低于==等关系运算符。因此，建议对于位运算符，尽量都加上括号保证运算顺序正确。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const int N=9,K=N*N;
int n,k,top;
//1:国王,0:空置
//cnt[i]:i在二进制下的 1 的个数
//ok[i]:第i个行内1不相邻的状态
//dp[i][j][k]:第i行,共放置j个国王,第i行是状态k
ll cnt[(1<<N+1)+1],ok[(1<<N+1)+1],dp[N+1][K+1][(1<<N+1)+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&k);
//预处理:cnt,ok.
for(int i=0;i<(1<<n);i++){
int pl=0,j=i;
while(j){
if(j&1)pl++;
j>>=1;
}cnt[i]=pl;
if(((i<<1)&i)==0)ok[++top]=i;
}//边界
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
//p,q:枚举第i行,第i-1行的状态
//[1,top]优化,剔除行内不满足的
for(int p=1;p<=top;p++){
int s1=ok[p];
for(int q=1;q<=top;q++){
int s2=ok[q];
//行间合法
if((((s2<<1)|s2|(s2>>1))&s1)==0){
//DP累加
for(int j=cnt[s1];j<=k;j++){
dp[i][j][s1]+=dp[i-1][j-cnt[s1]][s2];
}
}
}
}
}//输出
ll ans=0;
for(int i=1;i<=top;i++)ans+=dp[n][k][ok[i]];
printf("%lld\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
