bitset 维护01可行背包
给定 \(n\) 个数 \(a_1,\dots,a_n\)，已知 \(\sum a_i=O(n)\)，求一种把 \(a\) 分为两组的方案使得两组的和尽可能接近。
期望复杂度：\(O(n\sqrt n\log n/\omega)\)
解答
把 \(a_i\) 中相同的数合并，容易发现只有 \(O(\sqrt n)\) 种不同的 \(a_i\)，然后按照多重背包动态规划即可。
使用 bitset 优化即可做到 \(O(n\sqrt n\log n/\omega)\) 的时间复杂度。
动态 bitset
\(T\) 次询问，每次给定 \(n\) 个数 \(a_1,\dots,a_n\)，已知 \(\sum a_i=O(n)\)，求一种把 \(a\) 分为两组的方案使得两组的和尽可能接近。
期望复杂度：\(O(T+\sum n\sqrt n\log n/\omega)\)
解答：template trick
做法和上一个问题一样，但是必须保证每次询问的 bitset 大小都在 \(O(n)\) 才能保证正确的复杂度，这似乎意味着我们需要动态大小的 bitset。但可惜的是 C++ STL 中并没有支持动态大小的 bitset。
难道只能手写了吗？并非如此。一个最基本的想法是，我们每 \(2\) 的幂的长度（也即 \(2,4,8,16,\dots\)）次开一个 bitset，每次询问时选择长度合适的 bitset 使用。当然，我们不希望写太多重复的代码，而是使用模版来自动完成这个过程：
template<int len = 1>
int calc(int n) {
if (n > len)
return calc<std::min(len, maxn)>(n);
// 实际计算
bitset<len> f;
// ...
}