状态压缩DP学习笔记
状态压缩DP学习笔记
永远填不满的坑。
单纯只是为了防止状压DP忘得一干二净而写的。
关于状压DP
其实就是一种暴力的枚举，只有在数据很小时才能使用。一般情况下是 \(n \le 20\)。
比如说在方格中放置棋子，对于每个格子，都有放或不放两种可能，状压就是将每一种情况都表示出来，用二进制的形式。
比如在二进制下：$$0101(2)$$
就可以表示，第 \(1\) 和 第 \(3\) 个格子没有放，而第 \(2\) 和第 \(4\) 个格子放了。
因为涉及到进制转换，所以用到位运算的情况很多。
首先是基础的三个位运算
- 与：
&，二进制下对应位两个数均为 \(1\) 时值才为 \(1\)，否则为 \(0\)。 - 或：
|，二进制下对应位两个数有一个为 \(1\) 时值就为 \(1\)。 - 异或：
^，二进制下对应位两个数不同时值为 \(1\)，否则为 \(0\)。
下面只是列出一些例子：
- 右移一位：
x>>1 - 左移一位，并加上0/1：
x<<1 / x<<1+1 - 最后一位取反：
x^1 - 求二进制下 \(x\) 中有几个 \(1\)：
while(x)x&=(x-1),sum++; - 二进制下 \(x\) 的第 \(i\) 位是否为 \(1\)：
x&(1< - 有 \(x\) 个物品时的组合方法数：
(1<
2022/3/3