状压动态规划
flywen
·
·
算法·理论
Part.0 前言
鉴于我从学 oi 开始就不擅长喜欢动态规划，如今都以 NOIP 为目标，却连最基础的橙色动态规划题都没有思路，所以我决定从零开始学习动态规划。
这是一篇写给自己的动态规划入门学习笔记，但我也希望这能帮助到其他因没有学会动态规划而苦恼的选手。
状压动态规划，全名状态压缩动态规划，是一种较为基础的动态规划类型，由于其时间复杂度较高，故数据范围小，容易想到。然而掌握一些常用技巧，练习代码能力对于状压动态规划还是比较重要的，毕竟它不是很好写。
很多状压动态规划的计数问题都存在容斥解法，而且复杂度更优，希望大家不要看到小数据范围都只往状压想。
至于更进一层的 SOS 子集动态规划，本文不进行讨论。
---
### 记号约定
默认编号从 $1$ 开始，然而计算机中**二进制是从第 $0$ 位开始的**，所以请留意并区分文中的公式与代码。
由于常用到集合运算，而集合运算符号可能不方便理解，故我们使用一些非正式的符号，比如从集合 $S$ 中剔除元素 $x$ 的新集合表示为 $S-\{x\}$。
通常不区分时间复杂度渐进上界和渐进紧确界。时间复杂度中为显示代码流程有时不省略低阶项。
通常不严格要求各类求和等记号格式。
通常所有记号都是整数，如果没有取整符号，默认取下整。
---
### 代码
本人代码风格一坨，就看个乐吧。
尽量保持和正文一样的变量名。通常使用`s`表示状态。
---
### 相关链接
* [题单链接](https://www.luogu.com.cn/training/1022235)
* [更多的动态规划](https://www.luogu.com.cn/training/1022231)
# Part.1 模板
*本板块讲解状压动态规划基础题目和常用技巧。*
---
### [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433)
平面上 $n$ 个奶酪，从 $(0,0)$ 出发，至少要通过多少距离才能经过所有奶酪。
$n\leq15$。
---
考虑朴素的动态规划，定义 $f_{i,S}$ 为当前在 $i$ 号奶酪，经过奶酪集合为 $S$ 时的最小距离。对于 $i\in S$，转移为：
$$f_{i,S}=\min\limits_{j\in S}\{f_{j,S-\{j\}}+d_{j,i}\}$$
然而我们遇到一个问题：怎么快速的存，修改 $S$？
所以我们有**状压**，顾名思义，就是把复杂的状态信息通过某些方法，如二进制，压成能够便于计算的信息。
由于每个奶酪要么经过，要么没有经过，故令经过为 $1$，没经过为 $0$，$n$ 个奶酪的状态就可以用一个 $n$ 位二进制表示，记作 $s$。
因为 $j\in S$，$S-\{j\}$ 可以用位移表示为`s^(1<<(j-1))`。
时间复杂度 $O(n^22^n)$。
状压动态规划的代码相较于其他基础动态规划稍微困难一些，有些问题需要注意：
* 需要保证转移的状态已经计算，故建议先枚举状态 $s$。
* 还有就是在记号约定中提到的，计算机二进制是从第 $0$ 位开始的。
* 可以将初始位置作为一个奶酪，但是对复杂度影响较大，建议初始化。
```
for(int i = 1;i <= n;++i)f[i][1<<(i-1)] = sqrt(x[i] * x[i] + y[i] * y[i]);
for(int s = 0;s < (1<<n);++s){
for(int i = 1;i <= n;++i){
if(!(s&(1<<(i-1))))continue;
for(int j = 1;j <= n;++j){
if(!(s&(1<<(j-1))))continue;
f[i][s] = min(f[i][s],f[j][s^(1<<(i-1))] + dst[i][j]);
}
}
}
for(int i = 1;i <= n;++i)ans = min(ans,f[i][(1<<n)-1]);
```
---
### [P1171 售货员的难题](https://www.luogu.com.cn/problem/P1171)
$n$ 个村庄，从 $i$ 村庄走到 $j$ 村庄的距离为 $d_{i,j}$，求从 $1$ 号村庄出发经过每个村庄恰好一次并回到 $1$ 号村庄（不算经过）的最小距离。
$n\leq20$。
---
旅行商问题。
由上一题我们可知，状压动态规划的特征是 $n$ 很小，在 $21$ 以下。主要方法是将 $0/1$ 状态转化为整数的不同二进制位。
故这道题就被秒了，只需要在最后用从每个节点的全部经过状态走回 $1$ 号状态即可。
然而还有一个问题：如果不要求恰好一次呢？
很简单，用 floyd 计算传递闭包，就变成原问题了。
---
### [P3052 [USACO12MAR] Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052)/[P10483 小猫爬山](https://www.luogu.com.cn/problem/P10483)
$n$ 只牛，重量为 $w_i$。电梯载重为 $W$，求至少要用多少趟电梯才能运走所有牛。
$n\leq18$。
---
做法挺多的，个人喜欢先计算状态代价。
我们可以先预处理出所有的一个电梯能搭乘的牛方案的代价。
```
for(int s = 0;s < (1<<n);++s){
for(int i = 1;i <= n;++i){
if(s&(1<<(i-1)))cst[s] += w[i];
}
}
```
每个状态就可以由它的子集转移过来，即：
$$f_S=\min\limits_{s\in S}f_{S-s}+1$$
但是还有一个问题，就是怎么枚举子集？如果直接枚举复杂度直接平方。
先来看看实现十分简单的代码：
```
for(int s = S;s;s = (s - 1)&S);
```
正确性显然，因为每次循环后 $s$ 都会变为比 $s$ 小的，且仍为 $S$ 子集的最大集合。注意没有枚举空集。
那么枚举 $S$ 在枚举子集 $s$ 的复杂度是多少呢？
答案是 $O(3^n)$。考虑一个元素 $i$，它要么在 $s$ 和 $S$ 中都出现，要么只在 $S$ 中出现，要么在 $S$ 中没有出现。
对于枚举 $k$ 层子集，其复杂度为 $O((k+1)^n)$。此问题，相当于对全集枚举一个子集 $S$，再枚举 $S$ 的子集 $s$，故 $k=2$。
```cpp
for(int S = 0;S < (1<<n);++S){
for(int s = S;s;s = (s - 1)&S){
if(cst[s] <= W)f[S] = min(f[S],f[S - s] + 1);
}
}
```
### [P2396 yyy loves Maths VII](https://www.luogu.com.cn/problem/P2396)
$n$ 张牌，打出一张分数加 $a_i$，打完获胜，期间分数不能等于 $m$ 个特殊数字 $b_j$，求方案数，对 $10^9+7$ 取模。
$n\leq24,m\leq2$。
---
借这道题讲一下常用的 lowbit 优化。
状压是否使用卡牌的状态，时间复杂度 $O(2^nn)$，应该不用赘述：
```cpp
f[0] = 1;
for(int s = 1;s < (1<<n);++s){
long long d = 0;
for(int i = 1;i <= n;++i)if(s&(1<<(i-1)))d += a[i];
if(m && (d == b[1] || (m == 2 && d == b[2])))continue;
for(int i = 1;i <= n;++i)if(s&(1<<(i-1)))f[s] = (f[s] + f[s^(1<<(i-1))]) % mod;
}
printf("%lld",f[(1<<n)-1]);
```
这样的复杂度是卡满的，会被卡。
由于有一些元素不在集合中，我们可以通过二进制方法跳过枚举它们，即挑出目前最高位是 $1$ 的，再去除它，重复进行。
如何挑出最高位是 $1$ 的？那就是 lowbit，代码中可以写`i&(-i)`，原理可以看看[这个](https://blog.csdn.net/lesileqin/article/details/102418143)。
因为枚举全集，故能省去一半的复杂度，为 $O(2^{n-1}n)$。
```cpp
f[0] = 1;
for(int s = 1;s < (1<<n);++s){
for(int i = s;i;i -= i&(-i))d[s] += a[i&(-i)];
if(m && (d[s] == b[1] || (m == 2 && d[s] == b[2])))continue;
for(int i = s;i;i -= i&(-i))f[s] = (f[s] + f[s^(i&(-i))]) % mod;
}
printf("%lld",f[(1<<n)-1]);
```
---
至此，你已经基本了解状压动态规划的思想——利用二进制存储与操作 $0/1$ 集合。状压动态规划的题目特征为某数量（如节点，行列等）小于等于 $21$，围绕如何转化为 $0/1$ 以及当前状态和什么有关，如何快速转移等。
# Part.2 状压建模
*本板块主要讲解状压动态规划题目，难度主要提高及以上。*
## 逐行递推
*这种状压动态规划题目最为明显，其行列中会有一个数据范围很小，将其状压即可。*
---
### [P1539 [TJOI2011] 01矩阵](https://www.luogu.com.cn/problem/P1539)/[P1879 [USACO06NOV] Corn Fields G](https://www.luogu.com.cn/problem/P1879)
$n\times m$ 的矩阵，有些为 $0$，有些为 $1$，其余可以自由填写 $0/1$，求有多少种填写 $0/1$ 方案使得不存在任意两个 $1$ 相邻，对 $10007$ 取模。
$n\times m\leq25$。
---
首先取 $\min\{n,m\}$ 为状压的一排，实际编写时直接旋转矩阵就行，记 $n$ 为大的，$m$ 为小的。预处理当前排自己能够合法的状态，即满足`!(s&(s<<1))`，数量记作 $c$，远远小于 $2^m$。
对于当前行只和上一行有关，故枚举上一行即可。
数组再滚动一下。时间复杂度 $O(nc^2)$。
```cpp
f[0][1] = 1; //全0方案编号为1
for(int i = 1;i <= n;++i){
for(int j = 1;j <= cnt;++j){
int s = st[j]; //st是状态数组
if((s&s1[i]) != s1[i])continue; //s满足本行1的限制
if(((((1<<m)-1)^s)&s0[i]) != s0[i])continue; //s满足本行0的限制
for(int k = 1;k <= cnt;++k){
if(!(s&st[k]))f[i&1][j] = (f[i&1][j] + f[(i&1)^1][k]) % mod;
}
}
for(int j = 1;j <= cnt;++j)f[(i&1)^1][j] = 0; //清空下一行要用的
}
for(int i = 1;i <= cnt;++i)ans = (ans + f[n&1][i]) % mod;
```
---
### [P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896)
$n\times n$ 的矩阵，求有多少摆放 $k$ 个国王的方式，使得任意两个国王不能互相攻击（国王攻击时八邻格）。
$n\leq9,k\leq n^2$。
---
依旧将一行状态状压，预处理每行单独合法的状态，数量记作 $c$，远远小于 $2^n$，以及其中国王的数量，使用`__builtin_popcount`即可。
定义 $f_{i,j,S}$ 为第 $i$ 行状态为 $S$，已经放置 $j$ 个国王的方案数，那么转移只依赖于上一行。
时间复杂度 $O(n^3c^2)$。
```cpp
f[0][0][1] = 1;
for(int i = 1;i <= n;++i){
for(int cur = 1;cur <= cnt;++cur){
int s = st[cur];
for(int pre = 1;pre <= cnt;++pre){
int p = st[pre];
if((s&p)||((s<<1)&p)||(s&(p<<1)))continue;
for(int j = popc[pre];j + popc[cur] <= k;++j)f[i&1][j + popc[cur]][cur] += f[(i&1)^1][j][pre];
}
}
for(int cur = 1;cur <= cnt;++cur){
for(int j = 0;j <= k;++j)f[(i&1)^1][j][cur] = 0;
}
}
for(int cur = 1;cur <= cnt;++cur)ans += f[n&1][k][cur];
```
---
### [P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704)
$n\times m$ 的矩阵，有些地方为平原，有些地方为山丘。只有平原能部署炮兵阵地，要求炮兵阵地不能互相攻击，求最多能部署多少炮兵阵地。炮兵阵地攻击范围如下所示：
$n\leq10^2,m\leq10$。
---
把 $m$ 作为状压的维度。
先处理出每行单独合法的状态，设数量为 $c$。由于当前行不能攻击到自己，每行实际可行的状态数 $c$ 是很小的，实测大约 $c=60$。
当前行的炮兵阵地至多攻击到上两行的炮兵阵地，枚举前两行和当前行的状态即可，要求行之间不能互相攻击，并且当前行不能攻击到自己。
空间复杂度为 $O(nc^2)$。因为只关心上两行，故 $n$ 可以滚动掉；时间复杂度 $O(nc^3)$。
自己写写吧，写出来说明你已经大致掌握状压动态规划。
## 序列
*题目通常要求每一小段区间满足某要求，将其状压即可，其切面通常一位一位移动。*
### [P1357 花园](https://www.luogu.com.cn/problem/P1357)
一个长为 $n$ 的环形序列，每个位置为 $0/1$，任意 $m$ 个相邻位置的 $1$ 数量不能超过 $k$ 个。求方案数，对 $1000000007$ 取模。
$n\leq10^{15},2\leq m\leq\min\{n,5\},1\leq k<m$。
---
发现如果递推的话，当前状态只与前 $m-1$ 位有关，直接状压。不过无脑做时间复杂度为 $O(n2^m)$ 直接挂。
发现相同状态的转移是一致的（废话），转移还是线性的，再加上这明显的数据范围 $n\leq10^{15}$，显然就是矩阵快速幂。构造一个 $2^{m-1}\times2^{m-1}$ 的矩阵，最终答案即为矩阵对角线（第 $i$ 行 $i$ 列）之和。
时间复杂度 $O(2^{3m}\log n)$。
```
for(int i = 0;i < (1<<(m-1));++i){
int cnt = __builtin_popcount(i);
if(cnt > k)continue;
int j = (i<<1)&((1<<(m-1))-1);
++mt.v[i][j]; //在后面接0
if(cnt < k)++mt.v[i][j|1]; //在后面接1
}
mt = qpow(mt,n); //矩阵快速幂
for(int i = 0;i < (1<<(m-1));++i)ans = (ans + mt.v[i][i]) % mod;
```
---
### [P2157 [SDOI2009] 学校食堂](https://www.luogu.com.cn/problem/P2157)
$n$ 个学生排成队伍去打饭，第 $i$ 个学生的口味为 $t_i$。
食堂每次只能为一个学生做菜。若前一道菜的口味是 $x$，这一道为 $y$，则做这道菜所需的时间为 $x\oplus y$，做第一道菜不需要时间。
如果适当调换学生顺序，做菜的总时间会变短。但是学生不允许原来在 TA 后面的超过 $b_i$ 位同学在他之前打饭。
最小化总时间。
$n\leq10^3,b_i\leq7$。
---
状压 $b_i$，为方便，直接用 $7$ 就行。
定义 $f_{i,S,k}$ 为到 $i$ 位置，之前已经全部打完饭，后面 $[i,i+7]$ 的状态为 $S$，上一次给 $i+k$ 号打饭。
当 $i+1$ 已经打好时，即 $S\&1$ 为真时，将状态在队伍上右移：
$$f_{i+1,S>>1,k-1}\leftarrow f_{i,S,k}$$
否则，考虑下一个给 $i+l$ 打饭，显然转移比较复杂，写不出式子，看代码吧。
由于数组不接受 $k$ 是负数，需要平移一下。
时间复杂度 $O(n2^bb^3)$。
```cpp
void upd(int &u,int v){ u = min(u,v); }
f[1][0][-1 + 8] = 0; //上次完成0号(i+k=0)
for(int i = 1;i <= n;++i){
for(int s = 0;s < (1<<8);++s){
for(int k = -8;k < 8;++k){
if(i + k < 0 || i + k > n + 1)continue;
if(s&1)upd(f[i + 1][s>>1][k - 1 + 8],f[i][s][k + 8]); //i已完成,切面右移
else{ //i没完成,可以去完成下一个
for(int l = 0;l < 8;++l){ //枚举下一个完成i+l
if(i + l > n + 1)continue;
if(s&(1<<l))continue; //l已经完成
bool flag = 1;
for(int x = l - 1;x >= 0;--x){ //检查是否合法
if(!((s&(1<<x)) || l - x <= b[i + x])){
flag = 0; //判断没完成的i+x是否能接受去完成l
break;
}
}
if(!flag)break;
int cst = f[i][s][k + 8];
if(i + k)cst += t[i + k] ^ t[i + l];
upd(f[i][s + (1<<l)][l + 8],cst);
}
}
}
}
}
```
---
## 杂项
### [P2150 [NOI2015] 寿司晚宴](https://www.luogu.com.cn/problem/P2150)
$2$ 到 $n$ 这 $n - 1$ 个数中，挑出一些分为两组，使其两组间任意两个数互质，求有多少种合法方案，对 $p$ 取模。
$2\leq n\leq 500,p\leq10^9$。
---
注意到两组中质因数合集不可能有交，故将组中是否有某一质因数状压，然而 $500$ 以下的质数过多。
注意到每个数的最大质因数中至多有一种超过其算数平方根，故每个数至多有一中质因数大于等于 $23$，而 $23$ 以下只有 $c=8$ 个质因数，可以状压。
预处理每个数大于 $23$ 的质因数，按其排序。定义 $dp_{s1,s2}$ 为答案。每段开始时，我们定义 $f1_{s1,s2},f2_{s1,s2}\leftarrow dp_{s1,s2}$ 分别表示这一类大质因数分给第一组还是第二组，其小质因数分配情况分别为 $s1,s2$ 时的方案数。此类大质因数段结束时让 $dp_{s1,s2}\leftarrow f1_{s1,s2}+f2_{s1,s2}$。
时间复杂度 $O(n2^{2c}+n\log n)$。
```cpp
dp[0][0] = 1;
for(int i = 1;i < n;++i){
if(i == 1 || a[i].bp == -1 || a[i].bp != a[i - 1].bp)
for(int j = 0;j < (1<<8);++j)for(int k = 0;k < (1<<8);++k)
f1[j][k] = f2[j][k] = dp[j][k];
for(int j = (1<<8) - 1;j >= 0;--j){
for(int k = (1<<8) - 1;k >= 0;--k){
if(j&k)continue;
if(!(a[i].s&k))f1[j|a[i].s][k] = (f1[j|a[i].s][k] + f1[j][k]) % mod;
if(!(a[i].s&j))f2[j][k|a[i].s] = (f2[j][k|a[i].s] + f2[j][k]) % mod;
}
}
if(i == n - 1 || a[i].bp == -1 || a[i].bp != a[i + 1].bp)
for(int j = 0;j < (1<<8);++j)for(int k = 0;k < (1<<8);++k)
if(!(j&k))dp[j][k] = (f1[j][k] + f2[j][k] - dp[j][k] + mod) % mod;
}
for(int j = 0;j < (1<<8);++j)for(int k = 0;k < (1<<8);++k)
if(!(j&k))ans = (ans + dp[j][k]) % mod;
```
---
### [P2167 [SDOI2009] Bill的挑战](https://www.luogu.com.cn/problem/P2167)
$n$ 个长度为 $L$ 的字符串 $A_x$，其中一些小写字母，其它为`?`，表示随意填任何小写字母。求有多少种填写方式，使得**恰好** $k$ 个字符串相同，对 $1000003$ 取模。
$n\leq15,L\leq50$。
---
先处理一下第 $i$ 位有哪些串能放 $c$ 字符，状压为 $st_{i,c}$。
定义 $f_{i,S}$ 表示到第 $i$ 位，匹配上的字符串状态为 $S$ 时的方案数。转移就很简单了。
时间复杂度 $O(2^nLC)$，$C$ 表示字符集大小，为 $26$。
```cpp
f[0][(1<<n) - 1] = 1;
for(int i = 1;i <= len;++i){
for(int s = 0;s < (1<<n);++s){
for(char c = 'a';c <= 'z';++c)f[i][st[i][c - 'a']&s] = (f[i][st[i][c - 'a']&s] + f[i - 1][s]) % mod;
}
}
for(int s = 0;s < (1<<n);++s){
if(__builtin_popcount(s) == k)ans = (ans + f[len][s]) % mod;
}
printf("%d\n",ans);
```
---
### [P2465 [SDOI2008] 山贼集团](https://www.luogu.com.cn/problem/P2465)
给定一棵有 $n$ 个节点的树，$1$ 号节点为总部，现部署 $p$ 个分部，每一个分部的管辖范围定义为它到 $1$ 号节点的路径。给定在节点 $u$ 修建 $x$ 号分部的代价 $a_{u,x}$。
给定 $t$ 条其他信息，每条给定 $c$ 个分部编号，若它们的管辖范围有交，则**每个**都被管辖的村庄总收益加上（或减去） $v$。最大化收益。
$p\leq12,n\leq100,t\leq2^p$。
---
状压 $p$ 维度，表示节点被多少个分部管辖。定义 $f_{u,S}$ 表示 $u$ 节点作为总部时，$u$ 被管辖情况为 $S$，其子树的最大收益。初始化为 $f_{u,\{x\}}=-a_{u,x}$，利用此信息可以 $O(2^p)$ 完成其他状态的初始化：
```cpp
for(int s = 0;s < (1<<p);++s)f[u][s] = f[u][s^(s&-s)] + f[u][s&-s];
```
其实就是个 lowbit，很好理解。
然后上一个简单的树形背包就行。
对于额外信息，预处理一个村庄被集合 $S$ 管辖的**单一**收益 $v_S$。对于状态 $S$ 来说，总收益是其子集和，枚举子集是 $O(3^n)$。可以用高维前缀和加速，但不影响总复杂度，因为转移时也枚举子集了。
时间复杂度 $O(n3^p)$。
```cpp
void dfs(int u,int fa){
for(int s = 0;s < (1<<p);++s)f[u][s] = f[u][s^(s&-s)] + f[u][s&-s];
for(int i = 0;i < e[u].size();++i){
int v = e[u][i];
if(v == fa)continue;
dfs(v,u);
for(int s = (1<<p) - 1;s;--s){
for(int ss = s;ss;ss = (ss-1)&s)f[u][s] = max(f[u][s],f[u][s^ss] + f[v][ss]);
}
}
for(int s = 0;s < (1<<p);++s){
for(int ss = s;ss;ss = (ss-1)&s)f[u][s] += val[ss];
}
}
```
---
### [P2473 [SCOI2008] 奖励关](https://www.luogu.com.cn/problem/P2473)
$n$ 种宝物，价值为 $p_i$，可能为负数，能拿走宝物 $i$ 的前提是曾经已拿走过给定的宝物集合 $A_i$ 中的所有宝物至少一次。
随机抛出 $k$ 的个宝物，求若采取最优策略，平均情况能得多少分。
$k\leq100,n\leq15$。
---
定义 $f_{i,S}$ 表示第 $i$ 次宝物抛出，已经取到状态 $S$ 的最大期望得分。
然而一件严重的事情就是，有可能第 $i$ 轮压根就到不了 $S$ 状态。
所以我们可以倒着来，定义 $f_{i,S}$ 为第 $1$ 到第 $i-1$ 次状态为 $S$，第 $i$ 轮到第 $k$ 轮中的最大期望得分。
转移方程很好写：
$$f_{i,S}=\frac{1}{n}\sum_{j=1}^n\max\{f_{i+1,S},f_{i+1,S+\{j\}}+p_j|A_i\in S\}$$
注：若 $j\in S$，这里的 $S+\{j\}$ 就表示不变。
最终答案为 $f_{1,0}$。
时间复杂度 $O(nk2^n)$。
```cpp
for(int i = k;i >= 1;--i){
for(int s = 0;s < (1<<n);++s){
for(int j = 1;it <= n;++j){
if((s&st[j]) == st[j])f[i][s] += max(f[i + 1][s],f[i + 1][s | (1<<(j-1))] + p[j]);
else f[i][s] += f[i + 1][s];
}
f[i][s] /= n;
}
}
```
---
### [P2566 [SCOI2009] 围豆豆](https://www.luogu.com.cn/problem/P2566)
$n\times m$ 的网格中有 $d$ 个豆豆，每个位置在 $(ax_i,ay_i)$，价值为 $v_i$。还有一些障碍物`#`。
从任意没有障碍物和豆豆的点出发，可以上下左右移动，不能经过障碍物和豆豆，最后回到出发点。被围住的豆豆为**路径围成的多边形**内的豆豆。
最终收益为围住豆豆价值和减去步数，最大化收益。
$d\leq9,n,m\leq10$。
---
定义 $f_{x,y,S}$ 为走到 $(x,y)$，围住豆豆状态为 $S$ 的最小步数。对每个合法起点跑一个 bfs 即可。
难点在于如何在移动位置后更新 $S$。
对于最终路径，如果从一个豆豆向右引一条射线，那么它被围住当且仅当这条射线与路径（中**不与射线重合**的线段）交于奇数个点。
当竖向移动时，我们需要更新状态：
```cpp
int upd(int x,int y,int s,int nx,int ny){ //从(x,y)到(nx,ny)
for(int i = 1;i <= d;++i){
if(((y == ay[i] && ny < ay[i]) || (ny == ay[i] && y < ay[i])) && nx > ax[i])s ^= (1<<(i-1));
}
return s;
}
```
代码就是 bfs，时间复杂度 $O(n^2d2^d)$。
```
int dy[] = {0,1,0,-1},dx[] = {1,0,-1,0};
q.push({sx,sy,0});
f[sx][sy][0] = 0;
while(!q.empty()){
int x = q.front().x,y = q.front().y,s = q.front().s;q.pop();
vst[x][y][s] = 1;
for(int i = 0;i < 4;++i){
int nx = x + dx[i],ny = y + dy[i];
if(nx < 1 || ny < 1 || ny > n || nx > m || (c[ny][nx] >= '1' && c[ny][nx] <= '9') || c[ny][nx] == '#')continue;
int ns = s;if(i&1)ns = upd(x,y,s,nx,ny);
if(vst[nx][ny][ns])continue;
if(f[x][y][s] < f[nx][ny][ns]){
vst[nx][ny][ns] = 1;
f[nx][ny][ns] = f[x][y][s] + 1;
q.push({nx,ny,ns});
}
}
}
for(int s = 0;s < (1<<d);++s)ans = max(ans,st[s] - f[sx][sy][s]);
```
---
### [P3694 邦邦的大合唱站队](https://www.luogu.com.cn/problem/P3694)
$n$ 个人排成一排，第 $i$ 个人属于组 $a_i$，共 $m$ 组。求最小的出队人数，使得出列的人以选定位置回到队伍中，每个组的人是一个连续段。
$n\leq10^5,m\leq20$。
---
这题挺有意思的。
首先无脑状压每个组是否已经连续。
关键在于，最后的组顺序先后无关，可以将以完成的组合在一起，放在最前面。这件事我百思不得其解。
假设我们这样做，如果最优方案中一个组并不是按设想的一样放在前面，那么它根本就不可能成为最优方案。
所以就解决了，每次枚举一个没有被完成连续的组，然后可以计算出它将要占用的区间，利用前缀和可以知道该区间有多少原本就是这组的，计算代价即可。
时间复杂度 $O(nm+m2^m)$。
```cpp
for(int i = 1;i <= n;++i){
int x = in();
for(int j = 1;j <= m;++j)s[i][j] = s[i - 1][j];
cnt[x]++,s[i][x]++;
}
memset(f,0x3f,sizeof(f));
f[0] = 0;
for(int s = 1;s < (1<<m);++s){
int len = 0;
for(int i = 1;i <= m;++i){
if(s&(1<<(i - 1)))len += cnt[i];
}
for(int i = 1;i <= m;++i){
if(s&(1<<(i - 1)))f[s] = min(f[s],f[s^(1<<(i-1))] + cnt[i] - s[len][i] + s[len - cnt[i]][i]);
}
}
printf("%d",f[(1<<m)-1]);
```
---
### [P3959 [NOIP 2017 提高组] 宝藏](https://www.luogu.com.cn/problem/P3959)
$n$ 个点 $m$ 条边的连通带权图。从任意一个节点 $s$ 出发，依次开通所有节点，选定一条边 $(u,v)$，一个端点已开通，另一个没有，记作 $u$，开通 $u$ 的代价为边权 $w_{u,v}$ 与 $u$ 到起点 $s$ 经过的节点数 $L$ 的乘积。求开通所有节点的最小代价。
$n\leq12,m\leq10^3$。
---
$L$ 就是深度，故按深度来转移。
状压开通节点状态为 $S$。
预处理 $\mathrm{cost}(T,S)$ 表示用边直接连接，使节点集合 $T$ 变为 $S$ 的最小代价，不合法就赋为 $+\inf$。
转移方程就很简单了：
$$f_{d,S}=\min_{T\in S}f_{d-1,T}+d\times\mathrm{cost}(T,S)$$
有一个问题就是新加入的点连接的不一定是第 $d-1$ 层的节点，难道我们还要再加一维状态记录上一层有哪些点吗？
显然不用，因为如果它连到更上层的点，现在它深度更大，代价更高，不会作为更优决策影响结果。
时间复杂度 $O(n^23^n)$，预处理时使用 lowbit 增量式可以做到 $O(n3^n)$。
注意初始化起点。
```cpp
memset(dp,0x3f,sizeof(dp));
for(int s = 0;s <= n;++s)dp[0][1<<rt] = 0;
for(int d = 1;d < n;++d){
for(int s = 1;s < (1<<n);++s){
for(int t = (s-1)&s;t;t = (t-1)&s)dp[d][s] = min(dp[d][s],dp[d - 1][t] + d * cost[t][s]);
}
ans = min(ans,dp[d][(1<<n)-1]);
}
printf("%lld",ans);
```
---
### [P4484 [BJWC2018] 最长上升子序列](https://www.luogu.com.cn/problem/P4484)
求长为 $n$ 的随机排列最长上升子序列的期望值，对 $998244353$ 取模。
$n\leq28$。
---
设 $f_i$ 是在 $i$ 位置及之前时的最长上升子序列长度（可以不以 $i$ 结尾），那么对其进行差分为 $d_i$，则 $d_i$ 要么是 $0$，要么是 $1$，这是显然的。
既然如此，我们可以状压 $d$ 数组，定义 $dp_{i,d}$ 表示 $1$ 到 $i$ 的排列，$d$ 状态下的方案数，则答案为：
$$\frac{1}{n!}\sum\limits_{d=0}^{2^{n-1}-1}dp_{n,d}\times\mathrm{len}(d)$$
其中 $\mathrm{len}(d)$，表示 $d$ 中二进制位 $1$ 的个数，程序中可以使用`__builtin_popcount`求解。
我们可以钦定从小到大插入 $i$ 到位置 $k$，由于 $i$ 是最大的，故 $d_k=1$。而它后面第一个为 $1$ 的位置 $p$ 就应当 $d_p=0$，因为从这里开始 $i$ 对最长上升子序列的长度就没有影响了。
注意到 $d_1$ 为 $1$，可以少压一位，但时间复杂度 $O(n2^n)$ 依旧很难通过，所以——打表！
可以用[杨表（Young tableau）](https://harris.green/archives/dify-post-1774152478)高效解决，但不在本文讨论范围内，留一道要用杨表的题 [P3774 [CTSC2017] 最长上升子序列](https://www.luogu.com.cn/problem/P3774)，有兴趣可以去了解一下。
```cpp
fac = dp[1][0] = 1;
printf("1,\n");
for(int i = 2;i <= n;++i){
fac = (long long)fac * i % mod;
for(int d = 0;d < (1<<(i-2));++d){
if(!dp[(i^1)&1][d])continue;
dp[i&1][d] = ((long long)dp[i&1][d] + dp[(i^1)&1][d]) % mod; //将i插入到序列首位
for(int j = i - 2;j >= 0;--j){ //第j位
int nd = (d>>j)<<(j+1); //清空后j位
nd |= (1<<j); //第j位设置为1
int t = d&((1<<j)-1);
t = rem(t); //移除后面的最高位
nd |= t;
dp[i&1][nd] = ((long long)dp[i&1][nd] + dp[(i^1)&1][d]) % mod;
}
}
long long ans = 0;
for(int d = 0;d < (1<<(i-1));++d){
ans = (ans + (long long)dp[i&1][d] * (__builtin_popcount(d) + 1) % mod) % mod;
dp[(i^1)&1][d] = 0; //把下一次要用的清空
}
printf("%lld,\n",ans * inv(fac) % mod);
}
```