SOS DP

Cộng theo từng bit

Sau khi xử lý xong bit $0, \dots, b - 1$, gọi $F_b[m]$ là tổng $f[s]$ trên các $s \subseteq m$ mà $s$ và $m$ giống nhau ở mọi bit từ $b$ trở lên. Ban đầu $F_0 = f$. Xử lý bit $b$: nếu $m$ không có bit $b$ thì $s$ cũng không có, $F_{b+1}[m] = F_b[m]$. Nếu $m$ có bit $b$ thì $s$ có hoặc không có bit $b$, hai nhóm rời nhau: $F_{b+1}[m] = F_b[m] + F_b[m \oplus 2^b]$. Sau $B$ bit, $F_B[m]$ là tổng trên mọi tập con. Chỉ cần một mảng: duyệt $m$ theo bất kỳ thứ tự nào, vì $m \oplus 2^b$ không có bit $b$ nên không bị sửa trong cùng lượt.

for (ll b = 0; b < B; b++)
    for (ll m = 0; m < (1 << B); m++)
        if (m >> b & 1) F[m] += F[m ^ (1 << b)];

Vòng trong đi qua cả $2^B$ mặt nạ chỉ để bỏ một nửa. Các mặt nạ xếp thành từng khối dài $2^{b+1}$: nửa đầu khối không có bit $b$, nửa sau có. Đi theo khối thì vòng lặp chỉ chạm nửa cần cộng và không còn câu if:

for (ll b = 0; b < B; b++)
    for (ll m = 0; m < (1 << B); m += 2 << b)
        for (ll j = m; j < m + (1 << b); j++) F[j | 1 << b] += F[j];

Đi theo khối nhanh gần gấp đôi; cùng phép tính, chỉ đổi cách đi.

Tổng trên tập cha ($s \supseteq m$) đảo chiều: nếu $m$ không có bit $b$ thì cộng $F[m \oplus 2^b]$. Số phần tử giao khác rỗng với $x$ là tổng trừ số phần tử là tập con của phần bù của $x$.

Ví dụBa Góc Nhìn Của Mặt Nạ

Đề. Dãy $n \le 2 \cdot 10^5$ số tới $10^6$. Với mỗi $a_i$ đếm số $j$ có $a_j \subseteq a_i$, số $j$ có $a_j \supseteq a_i$, số $j$ có $a_i \mathbin{\mathrm{AND}} a_j \ne 0$.

Lời giải. $10^6 < 2^{20}$ nên mọi số là mặt nạ 20 bit. Câu một là tổng trên tập con, câu hai là tổng trên tập cha. Câu ba lấy phần bù: $a_j$ không giao $a_i$ khi và chỉ khi $a_j$ là tập con của $2^{20} - 1 - a_i$, nên đáp án là $n$ trừ số đó.

Bước 1: đếm. sub[x], sup[x] cùng bắt đầu bằng số lần $x$ xuất hiện.

cin >> a[i];
sub[a[i]]++;
sup[a[i]]++;

Bước 2: SOS hai chiều cùng lúc. Theo từng bit $b$: mặt nạ có bit $b$ cộng giá trị của mặt nạ tắt bit đó vào sub (gom từ tập con); mặt nạ không có bit $b$ cộng giá trị của mặt nạ bật bit đó vào sup (gom từ tập cha). Hai phép không đụng nhau nên làm chung một vòng. Sau khi xử lý các bit $0..b$, sub[m] là tổng trên các tập con chỉ khác $m$ ở các bit $0..b$; hết mọi bit thì là tổng trên mọi tập con.

for (ll b = 0; b < B; b++)
    for (ll m = 0; m < S; m++) {
        if (m >> b & 1) sub[m] += sub[m ^ (1 << b)];
        else sup[m] += sup[m ^ (1 << b)];
    }

Bước 3: trả lời. Câu ba tra sub ở phần bù (S - 1) ^ a[i].

cout << sub[a[i]] << ' ' << sup[a[i]] << ' ' << n - sub[(S - 1) ^ a[i]] << '\n';

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

const ll B = 20, S = 1 << B;
ll n, a[200005], sub[S], sup[S];

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sub[a[i]]++;
        sup[a[i]]++;
    }
    for (ll b = 0; b < B; b++)
        for (ll m = 0; m < S; m++) {
            if (m >> b & 1) sub[m] += sub[m ^ (1 << b)];
            else sup[m] += sup[m ^ (1 << b)];
        }
    for (ll i = 1; i <= n; i++) cout << sub[a[i]] << ' ' << sup[a[i]] << ' ' << n - sub[(S - 1) ^ a[i]] << '\n';
}

ChạyInput4
1 2 3 4

Output1 2 2
1 2 2
3 1 3
1 1 1

Ước lượng phép tính: $20 \cdot 2^{20} \approx 2 \cdot 10^7$ phép.

Giữ đại diện

Phép gộp không nhất thiết là cộng; bất kỳ phép kết hợp, giao hoán nào cũng được: max, min, OR, hay “giữ một phần tử bất kỳ”. Muốn với mỗi $x$ tìm một phần tử $y$ trong dãy có $x \mathbin{\mathrm{AND}} y = 0$, tức $y \subseteq \overline{x}$: lưu $F[m]$ là một phần tử (chẳng hạn lớn nhất) trong các phần tử là tập con của $m$, rồi tra $F[\overline{x}]$.

Ví dụNgười Bạn Không Giao Bit

Đề. Dãy $n \le 10^6$ số nhỏ hơn $2^{22}$. Với mỗi $a_i$, in một giá trị trong dãy không chung bit nào với nó, hoặc $-1$.

Lời giải. $a_j$ không chung bit với $a_i$ khi và chỉ khi $a_j$ là tập con của phần bù của $a_i$. Chỉ cần biết một phần tử bất kỳ trong các tập con của mỗi mặt nạ: SOS với phép max thay cho cộng.

Bước 1: khởi tạo. F[m] = -1 là chưa có phần tử nào; mỗi phần tử đặt chính nó vào ô của nó.

for (ll m = 0; m < S; m++) F[m] = -1;
for (ll i = 1; i <= n; i++) {
    cin >> a[i];
    F[a[i]] = a[i];
}

Bước 2: SOS với max. Sau cùng F[m] là phần tử lớn nhất trong các phần tử là tập con của $m$, hoặc $-1$.

for (ll b = 0; b < B; b++)
    for (ll m = 0; m < S; m++)
        if (m >> b & 1) F[m] = max(F[m], F[m ^ (1 << b)]);

Bước 3: tra ở phần bù (S - 1) ^ a[i]. F dùng int để mảng $2^{22}$ phần tử chỉ tốn 16 MB.

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

const ll B = 22, S = 1 << B;
ll n, a[1000005];
int F[S];

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

    cin >> n;
    for (ll m = 0; m < S; m++) F[m] = -1;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        F[a[i]] = a[i];
    }
    for (ll b = 0; b < B; b++)
        for (ll m = 0; m < S; m++)
            if (m >> b & 1) F[m] = max(F[m], F[m ^ (1 << b)]);
    for (ll i = 1; i <= n; i++) cout << F[(S - 1) ^ a[i]] << ' ';
    cout << '\n';
}

ChạyInput5
1 2 3 4 7

Output4 4 4 3 -1

Ước lượng phép tính: $22 \cdot 2^{22} \approx 9 \cdot 10^7$ phép max.

Bao hàm loại trừ

Đếm tập con có AND đúng bằng 0 khó, nhưng đếm tập con có AND chứa mặt nạ $m$ thì dễ: mọi phần tử được chọn phải là tập cha của $m$. Gọi $g[m]$ là số phần tử là tập cha của $m$ (SOS trên tập cha); số tập con không rỗng có AND $\supseteq m$ là $2^{g[m]} - 1$. Theo bao hàm loại trừ, số tập con có AND bằng 0 là

với $|m|$ là số bit 1 của $m$. Cũng theo khuôn này: hợp đúng bằng $S$ là đảo dấu theo tập con của số cách có hợp nằm trong mặt nạ con.

Ví dụGiao Bằng Không

Đề. Dãy $n \le 10^6$ số tới $10^6$. Đếm số tập con vị trí không rỗng có AND bằng 0, modulo $10^9 + 7$.

Lời giải. Đếm thẳng AND bằng 0 khó; dễ hơn là đếm các tập có AND chứa một mặt nạ $m$: đó là các tập con không rỗng của những phần tử chứa $m$. Rồi bao hàm loại trừ theo $m$ để chỉ giữ AND bằng đúng 0.

Bước 1: đếm phần tử chứa $m$. g[x] bắt đầu bằng số lần $x$ xuất hiện; SOS trên tập cha cho g[m] là số phần tử chứa $m$. Lũy thừa 2 tính sẵn ngay trong vòng đọc.

for (ll b = 0; b < B; b++)
    for (ll m = 0; m < S; m++)
        if (!(m >> b & 1)) g[m] += g[m ^ (1 << b)];

Bước 2: bao hàm loại trừ. pw[g[m]] - 1 là số tập không rỗng có AND chứa $m$. Cộng khi $m$ có chẵn bit 1, trừ khi lẻ: một tập có AND là $t$ được đếm ở mọi $m \subseteq t$ với tổng dấu $\sum_{m \subseteq t} (-1)^{|m|}$, bằng 1 khi $t = 0$ và bằng 0 khi $t \ne 0$.

for (ll m = 0; m < S; m++) {
    ll v = (pw[g[m]] - 1 + MOD) % MOD;
    if (__builtin_popcountll(m) & 1) ans = (ans - v + MOD) % MOD;
    else ans = (ans + v) % MOD;
}

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

const ll B = 20, S = 1 << B, MOD = 1e9 + 7;
ll n, g[S], pw[1000005];

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

    cin >> n;
    pw[0] = 1;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        g[x]++;
        pw[i] = pw[i - 1] * 2 % MOD;
    }
    for (ll b = 0; b < B; b++)
        for (ll m = 0; m < S; m++)
            if (!(m >> b & 1)) g[m] += g[m ^ (1 << b)];
    ll ans = 0;
    for (ll m = 0; m < S; m++) {
        ll v = (pw[g[m]] - 1 + MOD) % MOD;
        if (__builtin_popcountll(m) & 1) ans = (ans - v + MOD) % MOD;
        else ans = (ans + v) % MOD;
    }
    cout << ans << '\n';
}

ChạyInput3
1 2 3

Output2

Ước lượng phép tính: $20 \cdot 2^{20} \approx 2 \cdot 10^7$ phép.

Tích chập OR

Phép SOS trên tập con là một biến đổi $f \mapsto \hat f$ đảo được: chạy lại theo từng bit nhưng trừ thay cho cộng, $F[m] \mathrel{-}= F[m \oplus 2^b]$ khi $m$ có bit $b$, ta lấy lại $f$ (biến đổi Möbius). Với tích chập OR, $c_k = \sum_{i \mid j = k} a_i b_j$: tổng $\hat c[m]$ trên các $k \subseteq m$ là tổng trên các cặp $i, j$ cùng là tập con của $m$, tức $\hat a[m] \cdot \hat b[m]$. Vậy biến đổi $a$ và $b$, nhân từng điểm, rồi biến đổi ngược; tổng $O(B \cdot 2^B)$. Tích chập AND làm tương tự với tập cha.

Ví dụTích Chập OR

Đề. Hai dãy $a, b$ đánh chỉ số theo mọi mặt nạ $n \le 20$ bit. Tính $c_k = \sum_{i \mid j = k} a_i b_j$ modulo $998244353$.

Lời giải. Sau biến đổi tổng trên tập con, a[m] là tổng $a_i$ trên $i \subseteq m$, tương tự b[m]. Tích của chúng là tổng $a_i b_j$ trên mọi cặp có $i \mid j \subseteq m$, tức tổng của $c$ trên tập con của $m$. Vậy biến đổi $a$ và $b$, nhân từng điểm, rồi biến đổi ngược lấy lại $c$.

Bước 1: biến đổi và biến đổi ngược trong một hàm. zeta(f, 1) là SOS trên tập con theo mô-đun; zeta(f, -1) cùng vòng lặp nhưng trừ, là biến đổi ngược (Möbius). Đảo được vì mỗi bit là một phép biến đổi độc lập, và trừ hoàn tác đúng phép cộng. Phép trừ theo mô-đun cộng thêm MOD trước khi lấy dư, kết quả luôn trong $[0, p)$.

void zeta(ll f[], ll sign) {
    for (ll k = 0; k < n; k++)
        for (ll m = 0; m < S; m++)
            if (m >> k & 1) f[m] = (f[m] + sign * f[m ^ (1 << k)] % MOD + MOD) % MOD;
}

Bước 2: nhân từng điểm.

zeta(a, 1);
zeta(b, 1);
for (ll m = 0; m < S; m++) a[m] = a[m] * b[m] % MOD;
zeta(a, -1);

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

const ll MOD = 998244353;
ll n, S, a[1 << 20], b[1 << 20];

void zeta(ll f[], ll sign) {
    for (ll k = 0; k < n; k++)
        for (ll m = 0; m < S; m++)
            if (m >> k & 1) f[m] = (f[m] + sign * f[m ^ (1 << k)] % MOD + MOD) % MOD;
}

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

    cin >> n;
    S = 1 << n;
    for (ll i = 0; i < S; i++) cin >> a[i];
    for (ll i = 0; i < S; i++) cin >> b[i];
    zeta(a, 1);
    zeta(b, 1);
    for (ll m = 0; m < S; m++) a[m] = a[m] * b[m] % MOD;
    zeta(a, -1);
    for (ll m = 0; m < S; m++) cout << a[m] << ' ';
    cout << '\n';
}

ChạyInput2
1 2 3 4
5 6 7 8

Output5 28 43 184

Độ phức tạp: $O(n \cdot 2^n)$.

Hai giá trị lớn nhất

Có bài cần cặp phần tử tốt nhất trong các tập con của $m$, như $\max A_i + A_j$ với $i \ne j$ đều là tập con của $m$. Mỗi ô $F[m]$ giữ hai chỉ số có giá trị lớn nhất (khác nhau). Gộp hai danh sách: lấy bốn ứng viên, bỏ chỉ số trùng, giữ hai lớn nhất. Hai danh sách của $m$ và $m \oplus 2^b$ có thể chứa chung một chỉ số (một tập con của cả hai), nên kiểm trùng theo chỉ số chứ không theo giá trị.

Ví dụHai Chỉ Số Tốt Nhất

Đề. Dãy $A$ đánh chỉ số $0..2^N - 1$ với $N \le 18$. Với mỗi $K \ge 1$, tìm $\max A_i + A_j$ trên các cặp $i < j$ có $(i \mid j) \le K$.

Lời giải. $i \mid j \subseteq m$ khi và chỉ khi cả $i$ và $j$ là tập con của $m$. Vậy với mỗi $m$ chỉ cần hai chỉ số có giá trị lớn nhất trong các tập con của $m$: tổng của chúng là $best[m]$. Điều kiện $i \mid j \le K$ nghĩa là $i \mid j = m$ với một $m \le K$, nên đáp án là max tiền tố của $best$.

Bước 1: thêm một ứng viên. t1[m], t2[m] là chỉ số lớn nhất và nhì; $-1$ là chưa có. push bỏ qua chỉ số đã có (hai ô được gộp có thể cùng chứa một chỉ số), rồi chèn vào đúng vị trí.

void push(ll m, ll x) {
    if (x < 0 || x == t1[m] || x == t2[m]) return;
    if (t1[m] < 0 || A[x] > A[t1[m]]) {
        t2[m] = t1[m];
        t1[m] = x;
    } else if (t2[m] < 0 || A[x] > A[t2[m]]) t2[m] = x;
}

Bước 2: SOS. Ban đầu mỗi ô chỉ có chính nó. Mặt nạ bật bit $b$ gộp hai ứng viên của mặt nạ tắt bit đó.

for (ll b = 0; b < n; b++)
    for (ll m = 0; m < S; m++)
        if (m >> b & 1) {
            ll o = m ^ (1 << b);
            push(m, t1[o]);
            push(m, t2[o]);
        }

Bước 3: max tiền tố. ans chạy tăng dần theo $K$.

for (ll k = 1; k < S; k++) {
    if (t2[k] >= 0) ans = max(ans, A[t1[k]] + A[t2[k]]);
    cout << ans << '\n';
}

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

ll n, S, A[1 << 18], t1[1 << 18], t2[1 << 18];

void push(ll m, ll x) {
    if (x < 0 || x == t1[m] || x == t2[m]) return;
    if (t1[m] < 0 || A[x] > A[t1[m]]) {
        t2[m] = t1[m];
        t1[m] = x;
    } else if (t2[m] < 0 || A[x] > A[t2[m]]) t2[m] = x;
}

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

    cin >> n;
    S = 1 << n;
    for (ll i = 0; i < S; i++) {
        cin >> A[i];
        t1[i] = i;
        t2[i] = -1;
    }
    for (ll b = 0; b < n; b++)
        for (ll m = 0; m < S; m++)
            if (m >> b & 1) {
                ll o = m ^ (1 << b);
                push(m, t1[o]);
                push(m, t2[o]);
            }
    ll ans = 0;
    for (ll k = 1; k < S; k++) {
        if (t2[k] >= 0) ans = max(ans, A[t1[k]] + A[t2[k]]);
        cout << ans << '\n';
    }
}

ChạyInput2
1 4 2 3

Output5
5
7

Độ phức tạp: $O(N \cdot 2^N)$.