状压 DP
状压 DP，全称状态压缩 DP。是通过将状态以二进制形式压缩成一个整数来达到优化转移的目的。
引入：
例 $1$：
给定 $10$ 个整数，求取出 $3$ 个整数的异或和的最大值。
考虑到每个整数都有选/不选两种选择，因为可以将 $10$ 个整数的选择情况写成一个 $01$ 串，例如：$0100101000$ 表示选第 $4,6,9$ 个整数，不选第 $1,2,3,5,7,8,10$ 个整数。
而这个 $01$ 串，可以看成一个整数的二进制表示，例如 $0100101000$ 就可表示为：$296$。
因此，枚举 $[0,2^{10})$，对于仅有 $3$ 个 $1$ 的状态计算答案即可。
前置知识：
位运算符：
- $\And$：与，$a\And b=\begin{cases}1&a=1\land b=1\0&else\end{cases}$
- $|$：或，$a|b=\begin{cases}1&a=1\lor b=1\0&else\end{cases}$
- $\oplus$：异或，$a\oplus b=\begin{cases}1&a\neq b\0&else\end{cases}$（事实上，$\oplus$ 表示二元运算符，算法竞赛中一般用 $\oplus$ 作为异或）
- $\sim$：取反,$\sim a=\begin{cases}1&a=0\0&a=1\end{cases}$
- $<<$：左移，$a<<x=a\times 2^x$
- $>>$：右移，$a>>x=\lfloor\frac{a}{2^x}\rfloor$
基础位运算：
（第 $i$ 位均指从低位到高位）
- 取出二进制数第 $i$ 位：$x\And(1<<(i-1))$
- 去掉二进制数第 $i$ 位：$x\oplus(1<<(i-1))$
- 交集：$a\And b$
- 并集：$a|b$
- 补集：$a\oplus b$
- 子集：$a\And b=a$，$a$ 是 $b$ 的子集。
应用：
状压 DP 的思想是用二进制数表示事物的选/不选两种状态，而通过位运算达到简化代码、便于实现的目的。
旅行商问题：
例 $2$：
房间里放着 $n(n\leq 15)$ 块奶酪，一只小老鼠位于 $(0,0)$ 要把它们都吃掉，问至少要跑多少距离？
用 $0/1$ 表示某一块奶酪是否被吃，最后的结果就是所有的奶酪被吃。但是在转移时，两个状态之间的增量，在于两个奶酪之间距离，所以要知道某个状态所代表的路径上最后一个奶酪是那一个。因此，除了表示吃哪些奶酪的二进制数，还有加一维表示最后一个奶酪的状态。
状态：
设 dp$[x][y]$ 表示奶酪被吃的情况为 $x$，且最后一个吃的是第 $y$ 块奶酪的最短路径。
转移：
$(x,y)\leftarrow(x^{1<<(y-1)},z)(x\And(1<<(z-1))\neq0)$
DP 式子：
1 | For(j,1,(1<<n)-1) |
初始化：
完全没有吃奶酪时，不好处理“最后一个吃的奶酪”，所以可以初始化只吃了一个奶酪的状态。
时间复杂度：$O(n^22^n)$。
空间复杂度：$O(n2^n)$。
合法状态预处理：
例 $3$：
在一个 $n\times m(n\leq 10,m\leq10^3)$ 的方格图中，要求选择的任意两个方格之间没有重合的边。求总共有多少种选法。
通常按行处理，行列转置不影响。
一行的方格只会影响到与它相邻的两行，某一行的状态仅需要上一行的状态就可以转移。所以按顺序枚举行，分别枚举上一行和当前行的状态转移。
状态：
设 dp$[i][x]$ 表示前 $i$ 行且第 $i$ 状态为 $x$ 的方案数。
转移：
$(i,x)\leftarrow(i-1,y)$ $x,y$ 之间没有重合的边。
DP 式子：
1 | For(i,1,n) |
初始化：
第 $0$ 行状态只能为 $0$，初始化 dp$[0][0]=1$。
时间复杂度：$O(n4^n)$。
空间复杂度：$O(n2^n)$。
优化：
其一，考虑到，行内状态独立，所以可以预处理行内的合法状态，而不是在每层循环中都枚举一遍所有状态。
其二，对于一个确定的行状态，其下一行的状态集合也是确定的，所以还可以对于每一个行内合法状态，预处理出它的对应的下一行状态集合。
设每一个行内合法对应的下一行状态集合为 $g$，则优化后的时间复杂度为：$O(n\sum|g(x)|)$。
而且，由于状态只和相邻的两行有关，所以状态的第一维可以滚掉。空间复杂度优化至线性。
子集枚举：
例 $4$：
有 $n(n\leq16)$ 个人需要过桥，第 $i$ 个人的重量为 $w_i$，过桥用时为 $t_i$，这些人过桥时会被分成若干组，只有某一组的所有人全部过桥后，其余的组才能过桥。桥最大承重为 $W$，求这些人全部过桥的最短用时。
和例 $2$ 的区别在于此处每次不止能选择一个人，此处需要枚举一组的人，即：不是一个二进制位，而是一个二进制数。
其它部分相差不大。
状态：
设 dp$[x]$ 表示人是否过桥的状态为 $x$ 的最短用时。
转移：
$(x)\leftarrow(y)$ $y\And x=x\land w(x\oplus y)\leq W$。
DP 式子：
1 | For(i,1,(1<<n)-1) |
每一种状态的过桥时间和过桥体重可以预处理。
时间复杂度：$O(4^n)$。
空间复杂度：$O(2^n)$。
优化：
其一，使用例 $3$ 的方法，可以过桥的组是独立判断的，所以可以预处理哪些状态是可以过桥的，后枚举判断是否是子集。但此题是否可以过桥不像例 $3$ 那样的限制是固定的，所以在极端情况下并没有优化。
其二，预处理子集。考虑其时间复杂度，即：计算所有集合的子集大小之和，为 $O(3^n)$。
证明：
若一个状态有 $i$ 个 $1$，则其子集规模为 $O(2^i)$，考虑所有状态的 $1$ 的个数：$\sum\limits_{i=0}^n\binom{n}{i}\times 2^i\times 1^{n-i}=3^n$。
枚举方式：
枚举 $i$ 的子集，for(j=i;j;j=i&(j-1))