状态压缩动态规划（一）

[[ slider_text ]]

[[ item.c ]]

状态压缩动态规划（一）

发布时间 2024-08-09 作者：秋千月 来源：算法小站

状态压缩dp SOS dp

## 子集和
**问题描述**
给定长度为$$2^n$$的数组$$f$$，下标是$$0, 1, \cdots, 2^n - 1$$
求数组$$g$$，满足
```math
\displaystyle
g_i = \sum_{i \textbf{ and } j = j} f_j
```

### 算法分析
首先考虑$$i \textbf{ and } j = j$$具体表示什么
如果$$i$$的某一位是$$i_b = 0$$，对应的$$j_b = 0$$
如果$$i_b = 1$$，对应的$$j_b = \left< 0, 1 \right>$$

不放设$$i = 101$$，那么满足$$i \textbf{ and } j = j$$的值可能是$$\left< 000, 001, 100, 101 \right>$$
如果用$$1, 0$$表示这一位存不存在，那么$$i$$对应的集合是$$\left<1, 3 \right>$$
$$j$$对应的集合是$$\empty, \left<3 \right>, \left<1 \right>, \left<1, 3 \right>$$
换句话说，可以认为$$j$$的取值是$$i$$的**子集**，也就是说，对每个$$i$$，求$$i$$的子集和

```bash
for i = 0 to (1<<n) - 1
	for j = 0 to (1<<n) - 1
		if (i & j == j) g(i) += f(j)
```
这样的复杂度是$$O(4^n)$$，是不划算的，原因在于如果$$i = (00\cdots 0)_2$$，那么它的子集实际上只有$$1$$个
遍历到$$2^n - 1$$显然没有必要

> 可以考虑枚举子集

```bash
for i = 0 to (1<<n) - 1
	for j = i 的子集:    f(i) += g(j)
```
算法的时间复杂度是$$O(3^n)$$，计算方法不难
如果对于$$i$$，其二进制位有$$k$$个$$1$$，那么其子集个数是$$2^k$$
根据组合数，子集个数，这$$k$$位每一位都有$$2$$种选择，$$\left<0, 1 \right>$$，总共子集个数是$$2^k$$
那么需要枚举的子集数是$$\displaystyle \sum_{k = 0}^{n} \binom{n}{k} \cdot 2^k = (2+1)^n = 3^n$$

### 枚举子集代码实现
枚举子集的算法实现如下
```bash
for (int i = 0; i < (1 << n); i++) {
	int j = i;
	while (true) {
		g[i] += f[j];
		if (j == 0) break;
		j = (j - 1) & i;
	}
}
```

### 高维前缀和
> 二维前缀和怎么做

先考虑对每一行求前缀和，给定$$f(i, j)$$，求左上角的前缀和$$g(i, j)$$
```bash
for i = 1 to n,		for j = 1 to n:
		g(i, j) = g(i, j-1) + f(i, j)
```
然后再对每一列求前缀和
```bash
for i = 1 to n,		for j = 1 to n:
		g(i, j) = g(i, j) + g(i-1, j)
```

> 三维前缀和呢

```bash
for i, j, k:
	f(i, j, k) += f(i, j, k-1)
	
for i, j, k:
	f(i, j, k) += f(i, j-1, k)
	
for i, j, k:
	f(i, j, k) += f(i-1, j, k)
```

$$f_i$$，$$i$$最多是$$n$$位的二进制数，可以看作$$n$$维，每一维有`{0, 1}`两种取值
比如$$n = 4$$，可以看作`[2][2][2][2]`的数组

**子集和**，本质上就是一个**高维前缀和**
```bash
for i = 0 to n-1，枚举对哪一维求前缀和:
	for j = 0 to (1<<n)，枚举所有的数:
		如果发现它的第 i 位是 1，那么需要累加前缀和
		即 (? ? ? 1 ? ?) += (? ? ? 0 ? ?)
		
		if j >> i & 1:		f[j] += f[j - (1<<i)]
```

## Codeforces Round 112 (div 2) E
**问题描述**
给定$$n$$个数$$a_1 \cdots a_n$$，对于每个数$$i$$，找到另一个数$$j \neq i$$，满足$$a_i \textbf{ and } a_j = 0$$，或者判不存在

### 算法分析
对于每一个$$a_i$$，尝试找到$$a_j$$，满足以下条件
依次考虑每一位，如果对于某一位
$$(a_i) = 1$$，那么相应的位必须满足$$(a_j) = 0$$
$$(a_i) = 0$$，相应的$$(a_j) = \\{0, 1 \\}$$

注意到对$$a_i$$取反，$$a_i' \leftarrow \ \sim a_i$$，可以发现$$a_j$$恰好是$$a_i'$$的子集
$$a_i' \textbf{ and } a_j = a_j$$

于是，我们需要知道，对$$x \in [0, 2^{22} - 1]$$，每个$$x$$找到使得$$x \textbf{ and } a_j = a_j$$的**最小的**$$j$$

我们记 $$f(a_j) = \min(f(a_j), j)$$，记一下值等于$$a_j$$的最小下标
这个问题就转换成为，对于每个$$x \in [0, 2^{22}-1]$$，求
```math
\displaystyle
\min_{x \textbf{ and } y = y} f(y)
```

这个问题同样可以用类似子集和问题解决
```bash
for i = 0 to 22 bits 枚举每一位
	for x = 0 to (1<<22)-1 枚举每一个数
		if (x >> i & 1)，这一位如果是 1，需要跟这一位的子集取 min
			f(x) = min( f(x), f(x - (1<<i))  )
```

特别说明，对于**取反**，常见的做法是
```bash
let x = (11...1) - a[i]
// x 就是 a[i] 取反后的值
```

## Codeforces Round 225 (div1) E
**[Codeforces Round 225 (Div. 1)](https://codeforces.com/problemset/problem/383/E)**
**问题描述**
有$$n$$个数$$a_1, a_2, \cdots, a_n$$，每个数都是$$0 \sim 2^{24}-1$$
对于所有的 $$S \in [0, 2^{24}-1]$$，有多少个$$i$$满足 $$a_i \textbf{ and } S \neq 0$$
每个$$S$$都求出这样的答案，然后对答案求$$\oplus$$和
这里有限制是，对于每一个$$a_i$$，它的二进制表示中$$1$$的个数$$\leqslant 3$$

### 算法分析
注意到，对于$$S$$，如果$$a_i \textbf{ and } S = 0$$，相当于$$a_i$$是$$(\sim S)$$的一个子集
这个问题要求$$\neq 0$$，直接用$$n$$减去$$=0$$的答案即可，具体来说
如果求$$=0$$，答案就是$$(\sim S)$$的**子集个数**，$$\neq 0$$只要让$$n$$减去答案即可
```bash
先统计子集个数 f[...]
for i = 1 to n
		f( a[i] ) += 1

对 f[x] 求子集和，即统计每个数 x 的子集个数
for i = 0 to 24,  for x = 0 to (1<<24)
		if (x >> i & 1)		f[x] += f[x - (1<<i)]
		
对于每一个 S，答案是 n - f[~S]
f[~S] 可以用 f[  (1<<24)-1-S  ] 表示
```

## 子集问题扩展
### 超集和
```math
\displaystyle
g_i = \sum_{i \textbf{ and } j = i } f_j
```
实际上就是对每个集合$$i$$，求出满足$$i \subseteq j$$的$$f_j$$的和

若 $$i = 0, j = 0, 1$$
若 $$i = 1, j = 1$$
```bash
for i = 0 to n, for x = 0 to (1<<n)
		if (x >> i & 1) == 0:		f(x) += f(x + (1<<i))
```

### and 卷积
**问题描述**
给定长度为$$2^n$$的数组$$f, g$$，下标是$$0, 1, \cdots, 2^n - 1$$
求数组$$h$$，满足
```math
\displaystyle
h_i = \sum_{j \textbf{ and } k = i} f_j \times g_k
```

**算法分析**
```bash
for i = 0 to (1<<n), for j = 0 to (1<>n)
		h( i and j ) += f(i) * g(j)
```

这是暴力的做法，考虑到 $$j \textbf{ and } k \to i$$，我们有
$$(1, 1) \to 1$$
$$\\{ (0, 1), (1, 0), (0, 0) \\} \to 0$$
实际上
```math
\displaystyle
h_i = \sum_{\min(j, k) = i} f_j \cdot g_k
```
对于$$\min(j, k) = i$$，分为以下几种情况
$$j = i, k > i$$
$$j > i, k = i$$
这样，不妨考虑**后缀和**
```math
\displaystyle
F_j = \sum_{k \geqslant j} f_k \\
G_j = \sum_{k \geqslant j} g_k \\
H_j = \sum_{k \geqslant j} h_k
```
而注意到
```math
h_i = \sum_{\min(j, k) = i}, \quad H_i = \sum \left[ \min(j,k) = \{n, n-1, \cdots, i\} \right]
```
卷积可以写成如下形式
```math
\displaystyle
H_i = \sum_{\min(j, k) \geqslant i} f_j \cdot g_k = \sum_{j \geqslant i, k \geqslant i} f_j \cdot g_k
```
由于$$j, k$$相互独立，实际上就是
$$H_i = F_i \cdot G_i$$

### and 卷积扩展
对于高维情况
```math
f(i1, i2), g(j1, j2)
```
我们有
```bash
for i1, i2, j1, j2
	h( min(i1, j1), min(i2, j2) ) += f(i1, i2) * g(j1, j2)
```
同样记后缀和
```math
\displaystyle
F_{i, j} = \sum_{i'\geqslant i}\sum_{j'\geqslant j} f_{i',j'} \\
G_{i, j} = \sum_{i' \geqslant i} \sum_{j' \geqslant j} g_{i', j'} \\
H_{i, j} = \sum_{\min(i1, i2) \geqslant i, \min(j1, j2) \geqslant j} f_{i1, i2} \cdot g_{j1, j2} = F_{i, j} \cdot G_{i, j}
```
从集合的角度来看
```math
\displaystyle
F_j = \sum_{j \textbf{ and } j' = j} f_{j'}, \quad G_j = \sum_{j \textbf{ and } j' = j} g_{j'} \\
F_T = \sum_{T \subseteq T'} f_{T'} \\
H_T = \sum_{T \subseteq T'} h_{T'} = \sum_{T \subseteq (S1 \cap S2)} f_{S1} \cdot g_{S2} = \left(\sum_{T \subseteq S1} f_{S1} \right) \cdot \left( \sum_{T \subseteq S2} g_{S2} \right) = F_T \cdot G_T
```

> 如何从$$H$$求出$$h$$

先依次做后缀和，从$$f, g$$分别得到$$F, G$$，这样$$H = F \cdot G$$
那么知道后缀和（或者前缀和），怎么求原数组？可以用**差分**，高维情况就对每一维差分
```bash
for i = n downto 1
	for j = n downto 1
		f(i, j) -= f(i, j-1)

// 这样就变成了一维前缀和，关于 f[1...i] 这一维的前缀和

for i, j
	f(i, j) -= f(i-1, j)
```
将$$f, g$$做一个后缀和得到$$F, G$$，$$H = F \cdot G$$，然后对$$H$$做差分

### 算法实现
给定两个长度为$$2^n$$的数组
```math
f_0, f_1, \cdots, f_{2^n - 1}, \quad g_0, g_1 \cdots, g_{2^n - 1}
```
求出
```math
h_0, h_1, \cdots, h_{2^n - 1}
```
满足$$\displaystyle h\_i = \left( \sum\_{k \textbf{ and } j = i} f_j \cdot g_k \right) \bmod (10^9 + 7)$$

```bash
// 首先对 f[...] 和 g[...] 分别求后缀和，然后令 f[...] *= g[...]
// 再对 f[...] 作后缀差分

for (int i = 0; i < n; i++) {
	for (int x = 0; x < (1<<n); x += 1) {
		if ( (x >> i & 1) == 0 ) f[x] += f[x + (1<<i)], g[x] += g[x + (1<<i)]; 
	}
}

for (int x = 0; x < (1<<n); x += 1) {
	f[x] %= mod, g[x] %= mod;
	f[x] = f[x] * g[x] % mod;
}

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

for (int x = 0; x < (1<<n); x += 1) {
	f[x] %= mod;
	if (f[x] < 0) f[x] += mod;
}

ll ans = 0;
for (int x = 0; x < (1<<n); x += 1) ans ^= f[x];
```

## Codeforces Round 257 (div 1) D
**[Codeforces Round 257 (div 1) D. Jzzhu and Numbers](https://codeforces.com/problemset/problem/449/D)**
**问题描述**
给定$$n$$个非负整数$$a_1, \cdots, a_n$$，问有多少个非空子集，满足所有数 and 起来等于$$0$$

### 算法分析
集合问题，不妨考虑下 and 卷积，类似
```math
\displaystyle
h_{k} = \sum_{a_i \textbf{ and } a_j = k} g_{a_i} \cdot f_{a_j}
```
这样就构造出了集合的形式
不妨记$$h_i$$表示满足**子集 and 起来**$$= i$$的，这样的子集个数，答案就是$$h_0$$

从集合的角度来看
> 如果用$$h_T$$表示方案数呢？

$$h_T$$表示方案数，满足选一些元素使得
```math
B_{k1} = \{b_1, b_2, \cdots, b_{k1} \}, \quad T = b_1 \textbf{ and } \cdots \textbf{ and } b_{k1}
```
由于我们所需要知道的是，满足**子集and**$$= T$$的个数，所以实际上我们要求
```math
\displaystyle
H_T = \sum_{T \subseteq T'} h_{T'}
```
实际上，我们根据上面的分析，对于条件
```math
T = b_1 \textbf{ and } \cdots \textbf{ and } b_{k1} \\
\Rightarrow T \subseteq b_1, T \subseteq b_2, \cdots,T \subseteq b_{k1}
```
回到本例中，只需要统计满足$$T \subseteq a_{i}$$的，这样的$$i$$的个数$$cnt$$
$$H_T = 2^{cnt}$$，差分求出$$h_T$$即可

> 那么现在的问题转换成，对于每一个$$x$$，要求出多少个$$i$$满足$$x \subseteq a_i$$

实际上就是对于每个$$x$$，$$f[\cdots]$$记一下元素出现的次数，统计
```math
\displaystyle
\sum_{x \textbf{ and } a_i = x} f_{a_i}
```
对于每一个$$x$$，做一遍** and 后缀和**即可

### 算法实现
```bash
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[a[i]] += 1;

pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * 2;

for (int i = 0; i < M; i++) {
        for (int x = 0; x < (1<<M); x += 1) {
            if ((x >> i & 1) == 0) f[x] += f[x + (1<<i)];
        }
    }

for (int i = 0; i < (1<<M); i += 1) f[i] = pw[ f[i].val() ];

for (int i = 0; i < M; i++) {
        for (int x = 0; x < (1<<M); x += 1) {
            if ((x >> i & 1) == 0) f[x] -= f[x + (1<<i)];
        }
    }

auto ans = f[0].val();
    printf("%d\n", ans);
}
```

上一篇：区间dp在算法竞赛中的应用下一篇：状态压缩动态规划（二）

看完文章有啥想法