# Bitset：把一排布尔状态压进机器字

## 本节目标

学完后，你应能：

- 估算 `std::bitset<N>` 的时间与空间，而不是把它误当成真正的 $O(1)$ 集合；
- 用按位与、或、异或、移位和 `count` 表达集合交、并、对称差、平移与计数；
- 识别“布尔状态很多、转移相同、可按 64 位并行”的优化机会；
- 处理静态图三角形、奇偶多重集变换和带单点修改的字符串匹配；
- 判断什么时候编译期定长 `bitset` 不能用，需改成 `vector<uint64_t>`。

## 前置知识与课前自测

前置：位运算、集合、复杂度、基础数论中的整除与 Möbius 反演概念。

1. 两个长度 $10^5$ 的 `bitset` 做一次 `&`，复杂度是 $O(1)$ 吗？
2. `a << k` 对集合下标表示什么？移出范围的位怎样处理？
3. 若只关心计数奇偶，多重集合的“相加”对应 OR 还是 XOR？

<details><summary>自测答案</summary>

1. 不是，约需处理 $\lceil10^5/w\rceil$ 个机器字，复杂度 $O(N/w)$，通常 $w=64$。
2. 每个置位下标增加 $k$；越界位丢弃，低端补零。
3. XOR，因为 $1+1\equiv0\pmod2$；OR 会把两次出现错误保留为一次。

</details>

## 问题动机：为什么能快约 64 倍

若用 `bool` 数组检查两个点的公共邻居，一对点要逐个比较 $N$ 个位置。把 64 个布尔值装入一个无符号机器字，一次 `&` 同时完成 64 次“都是邻居吗”，再由硬件人口计数统计 1 的数量。算法没有少检查信息，而是改变了处理单位。

因此 bitset 优化的诚实复杂度应写成：

$$
O\left(\frac{N}{w}\right)\quad\text{每次整集合运算},\qquad w\approx64.
$$

当外层仍有 $N^2$ 对对象时，总量可能仍很大；必须结合数据范围估算机器字操作数。

## 步步式引导与核心操作

设第 $i$ 位表示元素 $i$ 是否在集合中：

- `A & B`：交集；
- `A | B`：并集；
- `A ^ B`：对称差，或模 2 意义下的加法；
- `~A`：补集，但会包含模板长度内所有高位，必须留意有效范围；
- `A << k` / `A >> k`：统一平移下标；
- `(A & B).count()`：交集大小。

字符串匹配中，若 `pos[c][i]=1` 表示位置 $i$ 是字符 $c$，模式第 $j$ 位要求起点 $p$ 满足 `pos[pattern[j]][p+j]=1`。右移 $j$ 后，这个条件被对齐到起点 $p$：

$$
match=\bigcap_{j=0}^{|y|-1}\left(pos[y_j]\gg j\right).
$$

这正是“先对齐，再取交”的通用思路。

## 实现指南与边界

- `std::bitset<N>` 的 $N$ 必须是编译期常量；运行期长度或频繁新建超大临时集合时，可手写 `vector<uint64_t>`。
- 下标从 0 开始最自然；从题目 1-based 转换时只做一次 `--i`。
- 最后一个机器字的无效高位要清零；`std::bitset` 会自动处理，手写动态位集不会。
- `_Find_first/_Find_next` 是 libstdc++ 扩展，不属于 C++17 标准；课程主代码不依赖它们。
- 在栈上放大量 bitset 可能爆栈；大数组放全局或堆上的 `vector`。

## 精选例题 1：Triangle

### 来源信息与题意

- VJudge：[AtCoder-abc258_g Triangle](https://vjudge.net/problem/AtCoder-abc258_g)
- 原题实际编号：[AtCoder ABC258 G](https://atcoder.jp/contests/abc258/tasks/abc258_g)
- 大致难度：提高；考点：邻接集合求交、重复计数

给一张 $3\le N\le3000$ 的简单无向图，输入为 $N\times N$ 邻接矩阵。求满足 $i<j<k$ 且三条边都存在的三元组数量。

<details><summary>Hint 1</summary>固定一条边 $(i,j)$，第三点必须同时是 $i,j$ 的邻居。</details>
<details><summary>Hint 2</summary>把每个点的邻居集合存成 bitset，公共邻居数是交集的 `count()`。</details>
<details><summary>Hint 3</summary>对每条无向边统计公共邻居后，每个三角形会由三条边各统计一次。</details>

### Observations、Editorial 与证明

为每行邻接矩阵建立 `neighbor[i]`。枚举 $i<j$，仅当 $(i,j)$ 是边时累加 `(neighbor[i] & neighbor[j]).count()`，最后除以 3。

任一被计数的公共邻居 $k$ 与 $i,j$ 三边齐全，构成三角形；每个三角形分别以其三条边作为枚举边，恰计三次，没有其他计数。复杂度最坏为 $O(N^3/w)$，约 $4.5\times10^6\times47$ 个 64 位块操作；答案用 `long long`。

### 核心伪代码与参考实现附件

```text
neighbor[i] = bitset of vertices adjacent to i
sum = 0
for every edge i-j with i < j:
    sum += popcount(neighbor[i] AND neighbor[j])
output sum / 3
```

完整 GNU C++17 参考实现见附件：[AtCoder-abc258_g.cpp](../../参考实现/03-Bitset/AtCoder-abc258_g.cpp)

### 复盘与变式

若是有向三环，不能直接除以 3；要先明确计数的是有序环还是点集。若图很稀疏，按度数分治或邻接表交集可能比固定扫描 3000 位更快。

## 精选例题 2：Alex and a TV Show

### 来源信息与题意

- VJudge：[CodeForces-1097F Alex and a TV Show](https://vjudge.net/problem/CodeForces-1097F)
- 原题：[Hello 2019](https://codeforces.com/problemset/problem/1097/F)
- 难度：2500；考点：整除 zeta 变换、模 2 多重集、bitset

维护 $n\le10^5$ 个多重集和 $q\le10^6$ 次操作。可把集合设为单元素，设为两个多重集之和，或设为两集合所有元素对 gcd 组成的乘积；查询值 $v\le7000$ 的出现次数模 2。赋值右侧先计算，所以编号可相同。

<details><summary>Hint 1</summary>直接保存每个值的奇偶时，“所有数对 gcd”仍近似二次。</details>
<details><summary>Hint 2</summary>令 $G_S[d]$ 为集合 $S$ 中能被 $d$ 整除的元素个数奇偶。</details>
<details><summary>Hint 3</summary>`gcd(a,b)` 被 $d$ 整除，当且仅当 $a,b$ 都被 $d$ 整除，所以乘积操作变成按位 AND。</details>
<details><summary>Hint 4</summary>由 $G[v]$（即"能被 $v$ 整除的元素奇偶"）恢复值 $v$ 的精确次数要做 Möbius 反演；模 2 下 $-1=1$，只需取所有非零 $\mu(k)$ 的 $G[vk]$ 异或。</details>

### Observations

1. 原坐标“值恰为 $v$”不适合 gcd 卷积；换到“能被 $d$ 整除”坐标后，gcd 条件分离成两个独立布尔条件。
2. 多重集相加在奇偶域 $\mathbb F_2$ 上是 XOR；数对笛卡尔积的奇偶是乘法，即 AND。
3. 变换后的 7000 个状态恰能放进约 110 个 64 位字，$10^6$ 次操作才可承受。

### Editorial 与正确性

为每个多重集保存 bitset $G[d]$。单元素 $v$ 在所有 $d\mid v$ 处置位；并操作为 XOR；gcd 乘积为 AND。查询时由

$$
cnt[v]=\sum_{k\ge1}\mu(k)G[vk]\pmod2
$$

恢复，模 2 下 $\mu(k)=1$ 与 $-1$ 贡献相同，$\mu(k)=0$ 不贡献。预处理每个 $v$ 对应的非零 Möbius 倍数掩码，交后 `count()%2`。

上述变换是可逆 Möbius 反演；三类更新在变换坐标中分别与原多重集定义等价，所以每次查询恢复的正是精确次数奇偶。每次二、三类操作和查询为 $O(7000/w)$，单元素赋值为 $O(\sqrt v)$；空间约 $n\cdot7001$ 位，约 88 MB，加预处理仍低于常见限制。

### 核心伪代码与参考实现附件

```text
state[x][d] = parity of elements in multiset x divisible by d   // G[d]
singleton(v): set exactly the divisor bits of v
union(y, z): state[x] = state[y] XOR state[z]
gcd_product(y, z): state[x] = state[y] AND state[z]
query(v): parity = popcount(state[x] AND squarefree_multiple_mask[v]) mod 2
```

完整 GNU C++17 参考实现见附件：[CodeForces-1097F.cpp](../../参考实现/03-Bitset/CodeForces-1097F.cpp)

### 复盘与变式

真正改变复杂度的是“换坐标后运算逐位化”，bitset 只是把逐位运算并行执行。若查询完整次数而非模 2，XOR/AND 不再表示整数加乘，需要换用数值数组和更昂贵的变换。

## 灵活性实验室：Substrings in a String

### 来源信息与题意

- VJudge：[CodeForces-914F Substrings in a String](https://vjudge.net/problem/CodeForces-914F)
- 原题：[Codecraft-18 / Codeforces Round 458](https://codeforces.com/problemset/problem/914/F)
- 难度：3000；考点：动态字符集合、位移对齐、重叠匹配

维护长度不超过 $10^5$ 的小写字符串，支持单点改字符，以及询问模式串 $y$ 在区间 $s[l..r]$ 中出现多少次，允许重叠。查询数不超过 $10^5$，所有询问模式长度之和不超过 $10^5$。

<details><summary>Hint 1</summary>为 26 个字符分别维护出现位置 bitset，单点修改只改两位。</details>
<details><summary>Hint 2</summary>模式第 $j$ 位对应 `position[y[j]] >> j`，把所有条件对齐到匹配起点。</details>
<details><summary>Hint 3</summary>取所有移位集合的交后，只保留起点区间 $[l-1,r-|y|]$。</details>

### Observations、Editorial 与证明

对每个字符维护位置集合。查询时初始化全 1 的 `match`，依次与 `position[y[j]] >> j` 取交；第 $p$ 位最终为 1 当且仅当所有 $s[p+j]=y[j]$。再右移到合法起点左端，并用一次左移让超出合法长度的高位溢出，`count` 即答案。

每个保留起点与一次真实出现一一对应，包括重叠出现。更新 $O(1)$；查询 $O(|y|\cdot |s|/w)$。模式总长度上界使总机器字操作可控。

### 核心伪代码与参考实现附件

```text
position[c] = bitset of indices currently containing c
update(i, c): clear i in old character set; set i in c
query(l, r, pattern):
    match = all_ones
    for offset, c in enumerate(pattern):
        match &= position[c] >> offset
    discard start positions outside [l, r-len(pattern)+1]
    return popcount(match)
```

完整 GNU C++17 参考实现见附件：[CodeForces-914F.cpp](../../参考实现/03-Bitset/CodeForces-914F.cpp)

### 复盘与变式

这题只与“普通字符串算法”部分相关，却很好地展示了“把不同偏移条件对齐到同一起点”。若模式总长度没有上界，最坏每次长度 $10^5$，该做法会退化；需要分块、自动机或其他离线结构。

## 扩展与联系

- 可达性传递闭包可把每行邻接关系存成 bitset，用 Warshall 的“整行 OR”优化到 $O(N^3/w)$。
- 背包可用 `reachable |= reachable << weight`；它依赖 0/1 选择。完全背包直接照抄会错误。
- 小质数集合常用单个 `uint64_t` 掩码，与线段树合并；`Please, another Queries on Array?` 将在高级线段树章节继续。

## 总结与自检

1. bitset 的真实复杂度为何含 $N/w$？
2. 三角形计数为什么除以 3？
3. gcd 多重集为何要换到“被 $d$ 整除的数量奇偶”坐标？
4. 动态字符串匹配中右移 $j$ 对齐的到底是什么下标？
5. 哪些情况下 `std::bitset` 应换成动态机器字数组？

## 课后训练建议

先独立完成 `Triangle`，再用 20 个随机小多重集手算 zeta 坐标理解第二题。`Alex and a TV Show` 不要求第一次就独立想出 Möbius 变换，但读完后必须能从 gcd 整除条件重新推导 AND。3000 分灵活题建议先写出三个字符位置集合的手算例，再展开完整实现。