这里记录有关 \(bitset\) 的一些知识点和实用技巧。
可以引起 \(O(\frac{n}{w})\) 优化的原理和操作：
- 原理：\(bitset\) 内置 \(long long\) 类型数组，每一位是一个 \(bit\)。因此实际操作时，若操作 \(n\) 位，则相当于只是对 \(\frac{n}{64}\) 个 \(longlong\) 类型的数字操作，\(n\) 很大时，复杂度可看作是 \(O(\frac{n}{64})\)。
- 操作：有关位运算的操作
eg:
int n;
bitset<N> a, b;
a <<= n; // O(n/w)
a &= b; // O(n/w)
实现可变长 bitset
定义一个 \(bitset\) 时， \(bitset\)<\(N\)> \(b\) 中的 \(N\) 必须是常量，如果为了实现多测而不得不用变量定义长度，则需要使用如下模板：
template <int maxn>
int solve(int n) // n 为 bitset 所需的大小
{if(maxn <= n){ // 复杂度为 O(logn) 级别的常数，可以忽略不计，目的是在多测情况下让bitset长度可根据n的大小随时调整 return solve<min(N, maxn << 1)>(n, k); }bitset<maxn> b;
// ...
}signed main()
{int T=1; cin>>T; while(T--){int n, k;cin >> n >> k;cout << solve<1>(n) << endl; }return 0;
}
上述代码中，使用函数模板定义了整数常量 \(maxn\)，并利用倍增和递归使得 \(maxn \leq n \leq 2 * maxn\)。实现了用 \(O(\log n)\) （可算作常数）的复杂度得到 略大于 \(n\)（不超过 \(2n\)，因此空间复杂度也可看作是 \(O(n)\)）的 常量，进而解决了多测且 \(n\) 之和固定的情况下定义变长的 \(bitset\)。
一些经典应用
- 优化 \(n, V\) 均为 \(1e5\) 级别的背包问题：前提是 \(dp\) 值必须是 \(bool\) 类型，这样可以将 \(bool\) 类型数组优化为 \(bitset\)，并且在转移过程中直接用位运算优化转移，总复杂度可优化为 \(O(\frac{nV}{w})\)，在时限宽松的情况下是可以通过的。
eg:
int n = 100000, V = 100000;
vector<bool> dp(V + 1);
for(int i = 1; i <= n; i ++){for(int j = V; j >= w[i]; j --){dp[j] |= dp[j - w[i]];}
}
可以优化为：
bitset<100000> dp;
for(int i = 1; i <= n; i ++){dp |= (dp << w[i]);
}
两个代码完全等价。
例题：CF div2 1048E2
\((upd...)\)