bitset神力

· · 算法·理论

有一说一 bitset 真是今年算法一匹黑马吧。很多老 stl 也都写过了，不吹不黑，本人 vector 9000 小时，multiset 2000 小时，set 3000 小时，map 4000 小时，pair 3000 小时，算法库里大多数 stl 都上千个小时，真感觉不出来和 bitset 有什么细节差距。只有 bitset 能给我一种刚接触 stl 时的感动。

用法

bitset 是 c++ 的一个 stl，类似于一个 bool 数组，每一位都是 0 / 1，大小位 1bit，可以支持位运算，空间复杂度是 O(\frac{n}{w})，w 是计算机的位数（不是没人告诉我那是 w 不是 \omega 啊）。

  1. 定义：bitset<V> b;，V 是 bitset 的位数，还可以 bitset<V> b("001011")，就可以初始化；

    （注意：这里是反向的，如果你此时调用 for (int i = 0; i < 6; i++) cout << b[i]; 那么输出的是 110100，不过似乎也没多少地方要这么用）

  2. 全局修改：b.set() / b.reset()：设为全 1 / 全 0，b.flip()：取反，时间复杂度 O(\frac{n}{\omega})；

  3. 单点修改：b[pos] = 0/1：直接访问，b.set(pos, val = 0/1)：将某位设为 0 / 1，b.reset(pos)：将某位设为 0，b.flip(pos)：pos 位取反，时间复杂度 O(1)；

  4. 位运算：将这些 0 / 1 视为二进制数与其他 bitset 进行二元位运算（与 / 或 / 异或…），或者左移 / 右移，时间复杂度 O(\frac{n}{\omega})；

  5. 单点访问：b[pos]，b.test(pos)：返回 pos 位的值，时间复杂度 O(1)；

  6. 全局访问：b.any()：b 中是否存在一位为 1，b.none()：b 中是否不存在一位为 1，b.count()：b 中 1 的数量，时间复杂度 O(\frac{n}{\omega})。

应用

维护集合

Set Operation

$1\le n\le 10^4, 1\le q \le 2\times10^5,1\le c_i\le 10^5$。

直接枚举 f[i][x] 表示第 i 个集合有没有 x 会死，O(qn) 是 2\times10^9 的，于是用 bitset 优化，带一个 \frac{1}{w} 的常数，就能过了。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e3 + 10, maxm = 1e4 + 10, mod = 1e9 + 7;
bitset<maxm> f[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;
            f[i][x] = 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        bool ff = 0;
        for (int i = 1; i <= n; i++) {
            if (f[i][l] && f[i][r]) {
                ff = 1;
                cout << "Yes" << endl;
                break;
            }
        }
        if (!ff) cout << "No" << endl;
    }
    return 0;
}

还有另外一种方式，用 f[x][i] 表示 x 数是否出现在 i 中，那么询问就是按位与再判断是否有 1 就好了，比较好写。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e3 + 10, int maxm = 1e4 + 10, mod = 1e9 + 7;
bitset<maxn> f[maxm];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            f[x][i] = 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ((f[l] & f[r]).any() ? "Yes" : "No") << endl;
    }
    return 0;
}

CF1097F Alex and a TV Show

$1\le n\le 10^5, 1\le x\le 7000, 1\le m\le 10^6$。

模拟赛题不会哭哭。

注意到模 2，于是可以拿 bitset 维护。

于是第一个操作直接改，第二个操作是异或，第四个操作直接查。

第三个操作不太好做，考虑每个 bitset 维护所有约数，那么第三个操作就是按位与。

预处理每个数的约数，第一个也秒了，第四个怎么办……

令原可重集为 A，约数可重集为 A'，查询 x 的个数，莫比乌斯反演：

\begin{align*} \sum_{a\in A}[a=x]&=\sum_{a\in A}[\frac{a}{x}=1]\\ &=\sum_{a\in A}\sum_{d|\frac{a}{x}}\mu(d)\\ &=\sum_{d\in A',x|d}\mu(\frac{x}{d}) \end{align*}

由于模 2，\mu(x) 相当于 x 有没有平方因数，预处理每个数没有平方因数的倍数，便可以 O(v\log v) 预处理，O(\frac{v}{\omega}) 单个操作。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 7e3 + 10, maxm = 1e5 + 10, mod = 1e9 + 7;
bitset<maxn> mu, a[maxm], pre[maxn], pre2[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);    
    int n, m;
    cin >> n >> m;
    mu.set();
    for (int i = 2; i * i < maxn; i++)
        for (int j = 1; j * i * i < maxn; j++)
            mu[i * i * j] = 0;
    for (int i = 1; i < maxn; i++)
        for (int j = 1; i * j < maxn; j++)
            pre[i * j][i] = 1, pre2[i][i * j] = mu[j];
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            a[x] = pre[y];
        }
        else if (op == 2) {
            int x, y, z;
            cin >> x >> y >> z;
            a[x] = a[y] ^ a[z];
        }
        else if (op == 3) {
            int x, y, z;
            cin >> x >> y >> z;
            a[x] = a[y] & a[z];
        }
        else {
            int x, y;
            cin >> x >> y;
            cout << ((a[x] & pre2[y]).count() & 1);
        }
    }
    return 0;
}

优化 dp

一般都是可行性 dp，或者状态是 bool 值的 dp，常见的有一系列背包问题。

简单瞎搞题、贪心只能过样例

$1\le n, l_i, r_i\le 100$。

由于数据范围很小可以转换为可行性问题，设 f_{i, j} 表示前 i 个数能不能达到 j，那么考虑枚举第 i 位的数 x，则 f[i][j] |= f[i - 1][j - x * x]。

很明显会炸，我们考虑用 bitset 的 f_i 表示前 i 个数能达到哪些数，那么状态栏的 j-x^2 就相当于左移了 x^2 位，于是 f[i] |= (f[i - 1] << (x * x))。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;

const int maxn = 1e2 + 10, maxm = 1e6 + 10, mod = 1e9 + 7;
bitset<maxm> f[maxn];
int l[maxn], r[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);    
    int n;
    cin >> n;
    f[0].set(0);
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    for (int i = 1; i <= n; i++) {
        for (int x = l[i]; x <= r[i]; x++) {
            f[i] |= (f[i - 1] << (x * x));
        }
    }
    cout << f[n].count();
    return 0;
}

P5020 [NOIP 2018 提高组] 货币系统

给你 n 种货币的面值，成为 A 货币系统，让你求出一个货币系统 B，使得 B 系统的货币种类不超过 A 系统，并且 A 系统能凑出的面值 B 系统也能凑出，A 系统不能凑出的面值 B 系统也不能凑出。

bitset 优化完全背包，式子就不推了，令 f[x] 表示 x 能不能表示出来，则 f[x] |= f[x - k * a[i]]，枚举 k 即可。

注意到 k = 3 时相当于 k = 1, k = 2 的情况叠加，k = 5 相当于 k=1, k=4 的叠加，所以只需要枚举 k=2^j 即可。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e5 + 10, maxm = 2.5e4 + 10,mod = 1e9 + 7; 
int a[maxn];
bitset<maxm> s;
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int t;
    cin >> t;
    while (t--) {
        s.reset();
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        s[0] = 1;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!s[a[i]]) {
                ans++;
                int x = a[i];
                while (x <= a[n]) s |= s << x, x <<= 1;
            }
        }
        cout << ans << endl;
    }
    return 0; 
}

其实不优化也能过（

高维偏序

用 bitset 做高维偏序是 O(\frac{n^2m}{w})，m 是维数。

具体来说你的 bitset<N> b[N] 记录的是 j 是否完全偏序 i，那么先按照每一维排序，得到每一维的 p_i，满足对于所有 j < k，a[p[i][j]][i] <= a[p[i][k]][i]，即每一维的升序的指针序列。

然后再记录一个 bitset<N> tmp，就可以在那个指针序列上，对每一位，用一个指针扫每一个小于等于那一位上数的位置，每扫过一个点就 tmp.set(pos)，直到扫不动了就让那一位 & 上 tmp，就得到了某一维上小于等于那一位的所有位置。

对每一维都扫一遍，最终为 1 的就是每一维都偏序的，所以每一位的偏序数就是 1 的个数。

没看懂的看代码（k 是维数）:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e5 + 10, mod = 1e9 + 7; 
bitset<maxn> b[maxn], tmp;
int a[maxn][10], p[10][maxn];
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> a[i][j];
            p[j][i] = i;
        }
    }
    for (int d = 1; d <= k; d++) sort(p[d] + 1, p[d] + n + 1, [=](int x, int y) { return a[x][d] < a[y][d]; });
    for (int i = 1; i <= n; i++) b[i].set();
    for (int d = 1; d <= k; d++) {
        tmp.reset();
        int id = 1;
        for (int i = 1; i <= n; i++) {
            while (id <= n && a[p[d][id]][d] <= a[p[d][i]][d]) tmp[p[d][id]] = 1, id++;
            if (1 <= p[d][i] && p[d][i] <= n) b[p[d][i]] &= tmp;
        }
    }
    for (int i = 1; i <= n; i++) cout << b[i].count() - 1 << endl;
    return 0; 
}

P3810 【模板】三维偏序（陌上花开）

注意到是 n\le10^5，bitset 开不下，需要分组 bitset，就是将 n 分成多个长为 B 的段，对每一段做上面的操作，所以 bitset 只需要开 B 的大小。

code:

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxb = 1e4 + 10, maxn = 1e5 + 10, mod = 1e9 + 7; 
bitset<maxn> b[maxb], tmp;
int a[maxn][5], ans[maxn], p[5][maxn], cnt[maxn];
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int n, k, len = 10000;
    cin >> n >> k;
    k = 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> a[i][j];
            p[j][i] = i;
        }
    }
    for (int d = 1; d <= k; d++) sort(p[d] + 1, p[d] + n + 1, [=](int x, int y) { return a[x][d] < a[y][d]; });
    for (int l = 1; l <= n; l += len) {
        int r = min(l + len - 1, n);
        for (int i = 1; i <= r - l + 1; i++) b[i].set();
        for (int d = 1; d <= k; d++) {
            tmp.reset();
            int id = 1;
            for (int i = 1; i <= n; i++) {
                while (id <= n && a[p[d][id]][d] <= a[p[d][i]][d]) tmp[p[d][id]] = 1, id++;
                if (l <= p[d][i] && p[d][i] <= r) b[p[d][i] - l + 1] &= tmp;
            }
        }
        for (int i = 1; i <= r - l + 1; i++) ans[l + i - 1] = b[i].count() - 1;
    }
    for (int i = 1; i <= n; i++) cnt[ans[i]]++;
    for (int i = 0; i < n; i++) cout << cnt[i] << endl;
    return 0; 
}