一、为什么要学 bitset
很多算法的内层循环在做 0/1 级别的批量操作：背包的可选状态、图的可达点集、集合的交并。std::bitset 把 N 个 0/1 压进 N/64 个机器字，一次 & | ^ ~ << >> 运算同时处理 64 位——复杂度直接除以 64，105 规模瞬间变得可过。它是 NOI 大纲 2025 修订版对提高级新增的考点，适合作为"隐蔽优化"出现在 DP / 图论题中。
生活类比：点名册上有 64 个学生，逐个打钩要 64 笔。bitset 相当于把 64 格印在一张模板上，"盖章"一次全部完成；与、或、异或就是两张模板叠在一起透光看。
二、位运算速查（bitset 的手工版）
| 操作 | 写法 | 用途 |
|---|---|---|
| 取第 i 位 | (x >> i) & 1 | 状态查询 |
| 置位 / 清位 | x | (1<<i) / x & ~(1<<i) | 加入 / 移除元素 |
| lowbit | x & -x | 树状数组、枚举集合元素 |
| 枚举子集 | for (t=S; t; t=(t-1)&S) | O(3k) 子集遍历 |
| popcount | __builtin_popcountll(x) | 元素个数统计 |
三、bitset 三大经典用法
① 0/1 背包按位优化
f 的 bitset 第 j 位 = 能否凑出重量 j；每来一件重 w 的物品：f |= f << w
一次移位 + 或运算完成整个内层循环。N=105 的可行性背包从 O(nN) 降到 O(nN/64)。
② 图上可达性传递（bitset 版 Floyd）
reach[u] 的第 v 位 = u 能否到达 v；转移：reach[v] |= reach[u]（u→v 有边时）
按拓扑序（或迭代若干轮）做"或传递"，n=104 时 Floyd 的 O(n³) 变 O(n³/64) ≈ 1.6×10⁷，轻松通过。
③ 集合交并与计数
两个 bitset 做 & 后 .count()，一次得到交集大小——莫队、二维偏序、查询"共同元素个数"类题目的常用加速。
f |= f << w 取代四、模板代码
#include <bitset>
const int N = 100005;
bitset<N> f;
f[0] = 1;
for (int i = 1; i <= n; i++) f |= (f << w[i]); // 0/1 背包可行性
if (f[m]) puts("YES");限制：bitset 长度必须是编译期常量。n 不固定时开最大长度，或手写
unsigned long long 数组版（一个循环做整块或运算）。五、易错点清单
<<移位量 ≥ 位宽是未定义行为：手写数组版时先整块移 word、再移余量。- 位运算优先级低于比较运算：
a & b == c实际是a & (b == c)，必须加括号。 - bitset 下标从 0 开始、
operator[]返回代理引用，批量统计用.count()而非逐位循环。 - 需要"可修改 + 查询单点 + 统计"混合操作时，bitset 不支持下标赋值以外的随机写——该用树状数组就别硬上。
六、练习
- P2709 小 B 的询问（配合莫队，体会位集合维护）
- 0/1 背包可行性、bitset 传递闭包各写一遍模板
- 组合：与状压 DP 对照——小集合用整数状压，大集合用 bitset