状压DP

状压 就是把几个维度压成一个维度, 通常是按 \(k\) 进制来压缩

如

dp[(1 << 1145141919810)]

这样相当于开了 \(1145141919810\) 个只有 \(0/1\) 的维度, 二进制下每一位表示这个维度

运行逝世

查询一个集合 \(s\) 的所有子集合

扩散行

for(int i = s; i < MAXN; i = (i + 1) | s){
  // s 是 i 的子集合
}

扩散行

for(int i = s; i; i = (i - 1) & s){
  // i 是 s 的子集合
}

时间复杂度

如果一个数二进制下有 \(i\) 个 \(0\), 子集数为 \(2^i\)

如果是 \(n\) 个数, 时间复杂度 \(\sum \limits_{i = 0}^n C_{n}^{i} \cdot 2^i = O(3^n)\)