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

若位运算仍像一串符号，先完成课前零食：把 64 个开关装进一个格子；其中也区分了 Bitset 与 SIMD 的关系。

本节目标

学完后，你应能：

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

前置知识与课前自测

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

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

自测答案

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

问题动机：为什么能快约 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
原题实际编号：AtCoder ABC258 G
大致难度：提高；考点：邻接集合求交、重复计数

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

Hint 1

固定一条边 $(i,j)$，第三点必须同时是 $i,j$ 的邻居。

Hint 2

把每个点的邻居集合存成 bitset，公共邻居数是交集的 `count()`。

Hint 3

对每条无向边统计公共邻居后，每个三角形会由三条边各统计一次。

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。

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

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

复盘与变式

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

精选例题 2：Alex and a TV Show

来源信息与题意

VJudge：CodeForces-1097F Alex and a TV Show
原题：Hello 2019
难度：2500；考点：整除 zeta 变换、模 2 多重集、bitset

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

Hint 1

直接保存每个值的奇偶时，“所有数对 gcd”仍近似二次。

Hint 2

令 $G_S[d]$ 为集合 $S$ 中能被 $d$ 整除的元素个数奇偶。

Hint 3

`gcd(a,b)` 被 $d$ 整除，当且仅当 $a,b$ 都被 $d$ 整除，所以乘积操作变成按位 AND。

Hint 4

由 $G[v]$（即"能被 $v$ 整除的元素奇偶"）恢复值 $v$ 的精确次数要做 Möbius 反演；模 2 下 $-1=1$，只需取所有非零 $\mu(k)$ 的 $G[vk]$ 异或。

Observations

原坐标“值恰为 $v$”不适合 gcd 卷积；换到“能被 $d$ 整除”坐标后，gcd 条件分离成两个独立布尔条件。
多重集相加在奇偶域 $\mathbb F_2$ 上是 XOR；数对笛卡尔积的奇偶是乘法，即 AND。
变换后的 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，加预处理仍低于常见限制。

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

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

复盘与变式

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

灵活性实验室：Substrings in a String

来源信息与题意

VJudge：CodeForces-914F Substrings in a String
原题：Codecraft-18 / Codeforces Round 458
难度：3000；考点：动态字符集合、位移对齐、重叠匹配

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

Hint 1

为 26 个字符分别维护出现位置 bitset，单点修改只改两位。

Hint 2

模式第 $j$ 位对应 `position[y[j]] >> j`，把所有条件对齐到匹配起点。

Hint 3

取所有移位集合的交后，只保留起点区间 $[l-1,r-|y|]$。

Observations、Editorial 与证明

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

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

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

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

复盘与变式

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

扩展与联系

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

总结与自检

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

课后训练建议

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

01-字级并行集合模型与动态匹配.md 11 KB Түүх Анхны өгөгдөл

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

本节目标

前置知识与课前自测

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

步步式引导与核心操作

实现指南与边界

精选例题 1：Triangle

来源信息与题意

Observations、Editorial 与证明

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

复盘与变式

精选例题 2：Alex and a TV Show

来源信息与题意

Observations

Editorial 与正确性

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

复盘与变式

灵活性实验室：Substrings in a String

来源信息与题意

Observations、Editorial 与证明

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

复盘与变式

扩展与联系

总结与自检

课后训练建议

01-字级并行集合模型与动态匹配.md 11 KB

Түүх Анхны өгөгдөл