【2024-ZR-C Day 8】动态规划（2）

1. 状压 DP

1.1. 子集枚举

for(int s = m; s; s = (s - 1) & m);

1.2. 状态压缩

1.2.1. 快速高维前缀和

对于一个 \(k\) 维数组，设每维的大小分别为 \((m_1, m_2, \cdots, m_k)\)，要访问的位置为 \((i_1, i_2, \cdots, i_k)\)，则用 \((\cdots(i_1 \cdot m_1 + i_2) \cdot m_2 + \cdots) + i_n\) 为下标，存入数组内。

于是我们可以用以下方式来书写每层只有 \(0\) 和 \(1\) 两个下标的 \(k\) 维前缀和。

int n = 1 << k;
for(int i = 0; i < k; i++)
for(int x = 0; x < (1 << k); x++)
	if((x >> i) & 1 == 0) f[x + (1 << i)] += f[x];

以上算法也称 FMT（快速莫比乌斯变换）。

1.2.2. 二进制压缩

考虑把一个长度为 \(n\) 的、能用 \(0/1\) 直接表示的状态压入一个整数。