Bitset

Bitset

bitset<N> b là $N$ bit, kích thước $N$ phải là hằng số lúc biên dịch; đặt theo giới hạn lớn nhất của đề. b[i] đọc hay gán một bit, b.set(), b.reset() bật hay tắt hết. Giữa hai bitset cùng kích thước có &, |, ^, ~; b << k dịch mọi bit lên chỉ số cao hơn $k$ vị trí, bit vượt quá $N - 1$ bị bỏ. b.count() đếm số bit 1, b.any() hỏi có bit 1 nào không, b._Find_first() và b._Find_next(i) nhảy tới bit 1 kế tiếp (hai hàm này riêng của GCC). Mọi phép trên cả bitset tốn $O(N / 64)$.

Bitset là một tập con của $\{0, \dots, N - 1\}$: AND là giao, OR là hợp, count là kích thước. Nhiều bài “đếm phần tử chung”, “tập các tổng đạt được”, “tập các đỉnh tới được” thành vài phép trên tập như vậy. Tập nhỏ hơn 64 phần tử thì một số ll cùng các phép bit (bài 14) là đủ; bitset dành cho tập lớn hơn.

Ví dụNăm Chuỗi Kết Quả

Đề. Hai chuỗi nhị phân $A, B$ dài $n \le 10^5$. In $A$ AND $B$, $A$ OR $B$, $A$ XOR $B$, NOT $A$, NOT $B$, mỗi kết quả một dòng $n$ ký tự.

Lời giải. Đọc hai chuỗi vào hai bitset<100000>, bit $i$ ứng với ký tự $i$, rồi dùng thẳng các toán tử. NOT đảo cả những bit từ $n$ trở đi, nên khi in chỉ in $n$ bit đầu. Không dùng hàm to_string, vì nó in bit cao trước và in đủ cả $10^5$ ký tự.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5;
ll n;
string s, t;
bitset<N> a, b;

void out(bitset<N> x) {
    for (ll i = 0; i < n; i++) cout << x[i];
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s >> t;
    for (ll i = 0; i < n; i++) {
        a[i] = s[i] == '1';
        b[i] = t[i] == '1';
    }
    out(a & b);
    out(a | b);
    out(a ^ b);
    out(~a);
    out(~b);
}

ChạyInput6
101100
110010

Output100000
111110
011110
010011
001101

Tổng con

Quy hoạch động tổng con (bài 12) giữ $\mathrm{ok}[s]$ là có chọn được tập con tổng $s$ không; thêm vật nặng $x$ thì $\mathrm{ok}'[s] = \mathrm{ok}[s] \lor \mathrm{ok}[s - x]$. Cả mảng $\mathrm{ok}$ là một bitset $b$, và công thức trên chính là b |= b << x: dịch $x$ tạo các tổng có dùng vật mới, OR giữ lại các tổng cũ. Không phải lo duyệt $s$ giảm dần như khi viết bằng mảng, vì b << x được tính từ bản cũ của $b$ trước khi OR.

Với $n$ vật và tổng tới $S$, chi phí là $O(nS / 64)$. Khi nhiều vật cùng khối lượng, tách mỗi nhóm $c$ vật giống nhau thành các gói $1, 2, 4, \dots$ và phần dư như trong bài cái túi giới hạn. Tổng các khối lượng khác nhau không quá $S$ thì chỉ có $O(\sqrt S)$ khối lượng khác nhau, chi phí còn $O(S \sqrt S / 64)$.

Thử với 2000 vật, tổng tới 100 nghìn:

Bitset nhanh hơn mảng bool cỡ 11 lần.

Ví dụCác Tổng Có Thể

Đề. $n \le 100$ đồng xu, giá trị tới 1000, tổng không quá $10^5$. In số tổng dương tạo được và liệt kê chúng tăng dần.

Lời giải. bitset<100001> b với b[0] = 1, mỗi đồng xu một lần b |= b << x. Số tổng dương là b.count() - 1, bỏ tổng 0. Chi phí $100 \cdot 10^5 / 64 \approx 1{,}6 \cdot 10^5$ phép trên từ máy.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll S = 1e5;
ll n;
bitset<S + 1> b;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    b[0] = 1;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        b |= b << x;
    }
    cout << b.count() - 1 << '\n';
    for (ll s = 1; s <= S; s++)
        if (b[s]) cout << s << ' ';
    cout << '\n';
}

ChạyInput3
2 3 7

Output7
2 3 5 7 9 10 12

Truy vết

Bitset chỉ nói tổng nào đạt được, không nói đạt bằng cách nào. Muốn in nghiệm, giữ lại bitset của từng tầng: $n + 1$ bitset dài $S$ tốn $nS / 8$ byte, với $n = 100$ và $S = 10^4$ chỉ khoảng 125 KB. Rồi đi từ tầng cuối về, hoặc từ tầng đầu tới, mỗi bước chọn một lựa chọn mà phần còn lại vẫn đạt được.

Muốn nghiệm nhỏ nhất theo thứ tự từ điển, quyết định từ vật đầu tiên trở đi, và với mỗi vật thử lựa chọn nhỏ trước. Để biết “phần còn lại vẫn đạt được”, dựng bitset theo hậu tố: $\mathrm{suf}_i$ là tập tổng tạo được từ các vật $i, \dots, n$.

Ví dụHai Mặt, Một Tổng

Đề. $N \le 100$ thẻ, thẻ $i$ chọn mặt H giá trị $A_i$ hoặc mặt T giá trị $B_i$, mỗi giá trị tới 100. Chọn mặt cho mọi thẻ để tổng bằng $S \le 10^4$; in No nếu không được, ngược lại Yes và chuỗi H/T nhỏ nhất theo thứ tự từ điển.

Lời giải. $\mathrm{suf}_{N+1} = \{0\}$ và $\mathrm{suf}_i = (\mathrm{suf}_{i+1} \ll A_i) \lor (\mathrm{suf}_{i+1} \ll B_i)$: mỗi thẻ bắt buộc chọn một mặt, nên không OR với bản cũ. $S \notin \mathrm{suf}_1$ thì in No. Ngược lại, với phần tổng còn thiếu $c$ (ban đầu $S$), thẻ $i$ chọn H nếu $c \ge A_i$ và $c - A_i \in \mathrm{suf}_{i+1}$, không thì chọn T. Với ví dụ, thẻ 1 chọn H còn thiếu 9, đạt được bằng $2 + 7$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll S = 1e4 + 1;
ll n, s, A[105], B[105];
bitset<S> suf[105];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    for (ll i = 1; i <= n; i++) cin >> A[i] >> B[i];
    suf[n + 1][0] = 1;
    for (ll i = n; i >= 1; i--) suf[i] = (suf[i + 1] << A[i]) | (suf[i + 1] << B[i]);
    if (!suf[1][s]) {
        cout << "No\n";
        return 0;
    }
    string res;
    ll c = s;
    for (ll i = 1; i <= n; i++) {
        if (c >= A[i] && suf[i + 1][c - A[i]]) {
            res += 'H';
            c -= A[i];
        } else {
            res += 'T';
            c -= B[i];
        }
    }
    cout << "Yes\n" << res << '\n';
}

ChạyInput3 10
1 5
2 4
3 7

OutputYes
HHT

AND hai hàng

Ma trận nhị phân $n \times n$ lưu mỗi hàng thành một bitset. Số cột mà hai hàng $i, j$ cùng có bit 1 là (r[i] & r[j]).count(), tốn $n / 64$ thay vì $n$. Duyệt mọi cặp hàng: $O(n^3 / 64)$, với $n = 3000$ là khoảng $2 \cdot 10^8$ phép trên từ máy, chạy dưới một giây.

Cùng cách đó kiểm hai tập có giao nhau, và đếm tam giác của đồ thị cho bằng ma trận kề (ô $(u, v)$ bằng 1 khi có cạnh nối $u$ với $v$). Trên đồ thị có hướng không chu trình còn dựng được tập đỉnh tới được từ mỗi $u$: nó là OR các tập của các đỉnh kề với $u$, tính theo thứ tự tô pô ngược (bài 32).

Ở đây bitset nhanh hơn khoảng 7 lần, ít hơn con số 64 vì trình biên dịch đã tự tối ưu vòng lặp bool. Dù vậy chênh lệch ấy vẫn đủ để qua giới hạn thời gian.

Ví dụBốn Góc Đen

Đề. Bảng $N \times N$ với $N \le 3000$, mỗi ô đen hoặc trắng. Đếm số hình chữ nhật (hai hàng khác nhau, hai cột khác nhau) có bốn góc đều đen.

Lời giải. Cố định cặp hàng $i < j$; gọi $c$ là số cột mà cả hai hàng đều đen. Mỗi cặp cột trong $c$ cột đó cho một hình chữ nhật, tức $\binom{c}{2}$. Tính $c$ bằng AND hai hàng rồi count. Có $4{,}5 \cdot 10^6$ cặp hàng, mỗi cặp $3000 / 64 \approx 47$ từ máy. Đáp án tới $\binom{3000}{2}^2 \approx 2 \cdot 10^{13}$, cần ll.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 3000;
ll n;
bitset<N> r[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < n; j++) r[i][j] = s[j] == '1';
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        for (ll j = i + 1; j < n; j++) {
            ll c = (r[i] & r[j]).count();
            ans += c * (c - 1) / 2;
        }
    cout << ans << '\n';
}

ChạyInput4
1100
1110
0110
1100

Output4

Ví dụBa Đỉnh Khép Kín

Đề. Đồ thị vô hướng $N \le 3000$ đỉnh cho bằng ma trận kề. Đếm số tam giác.

Lời giải. Với mỗi cạnh $(i, j)$, $i < j$, số đỉnh thứ ba kề cả hai là (r[i] & r[j]).count(). Mỗi tam giác có ba cạnh nên được đếm ba lần; chia 3 ở cuối. Đường chéo bằng 0 nên $i$ và $j$ không tự đếm vào phần giao.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 3000;
ll n;
bitset<N> r[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < n; j++) r[i][j] = s[j] == '1';
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        for (ll j = i + 1; j < n; j++)
            if (r[i][j]) ans += (r[i] & r[j]).count();
    cout << ans / 3 << '\n';
}

ChạyInput5
01100
10110
11010
01100
00000

Output2