Wiki › Thuật toán › Quy hoạch động (DP) › SOS DP (Sum over Subsets)

SOS DP (Sum over Subsets)

huunguyen Updated Tháng sáu 1, 2026

SOS DP (Sum over Subsets — tổng trên các tập con) là kỹ thuật tính, cho mọi mask trong khoảng $[0, 2^{N})$ , giá trị

$f [m a s k] = \sum_{s u b \subseteq m a s k} a [s u b]$

tức tổng của $a$ trên mọi tập con (submask) của $m a s k$ . Cách ngây thơ là với mỗi $m a s k$ duyệt hết các submask của nó; tổng số cặp $(m a s k, s u b)$ với $s u b \subseteq m a s k$ là $3^{N}$ (mỗi bit có 3 lựa chọn: nằm ngoài $m a s k$ , thuộc $m a s k$ nhưng ngoài $s u b$ , hoặc thuộc cả hai), nên cách đó tốn $O (3^{N})$ . SOS DP hạ xuống $O (N \cdot 2^{N})$ bằng cách xử lý từng bit một — với $N \leq 20$ thì $3^{N} \approx 3.5 \times 10^{9}$ là quá chậm, còn $N \cdot 2^{N} \approx 2 \times 10^{7}$ chạy thoải mái.

Kỹ thuật này còn là nền tảng cho zeta/Möbius transform trên lưới tập con và cho AND/OR/XOR convolution (tích chập bitwise).

Ý tưởng / Trực giác

Tại sao xử lý từng bit lại đúng? Ý tưởng cốt lõi là chia các submask theo từng bit.

Định nghĩa trạng thái trung gian:

$d p [i] [m a s k] = \sum a [s u b]$

với $s u b$ chạy trên các submask của $m a s k$ mà chỉ được phép khác $m a s k$ ở các bit $0, 1, \dots, i - 1$ (các bit từ $i$ trở lên của $s u b$ phải trùng $m a s k$ ).

Cơ sở: $d p [0] [m a s k] = a [m a s k]$ (chưa được tự do ở bit nào, nên $s u b = m a s k$ ).
Kết thúc: $d p [N] [m a s k] = f [m a s k]$ (được tự do ở tất cả các bit, nghĩa là mọi submask).

Chuyển tiếp khi thêm quyền tự do ở bit $i$ :

Nếu bit $i$ của $m a s k$ bằng $0$ : $s u b$ buộc phải có bit $i$ bằng $0$ (vì $s u b \subseteq m a s k$ ), nên thêm quyền tự do ở bit này không sinh thêm submask nào. Do đó $d p [i + 1] [m a s k] = d p [i] [m a s k]$ .
Nếu bit $i$ của $m a s k$ bằng $1$ : $s u b$ có thể chọn bit $i$ bằng $1$ (nhóm cũ, đã đếm trong $d p [i] [m a s k]$ ) hoặc bằng $0$ (nhóm mới). Nhóm mới chính là tất cả submask của $m a s k$ đã tắt bit $i$ — đúng bằng $d p [i] [m a s k \oplus (1 ≪ i)]$ . Vậy:

$d p [i + 1] [m a s k] = d p [i] [m a s k] + d p [i] [m a s k \oplus (1 ≪ i)]$

Điểm tinh tế giúp tiết kiệm bộ nhớ: khi đi từ tầng $i$ sang $i + 1$ , công thức cho mask có bit $i = 1$ dùng giá trị tầng $i$ của hai mask, mà mask $\oplus (1 ≪ i)$ có bit $i = 0$ nên giá trị của nó không thay đổi giữa tầng $i$ và $i + 1$ . Nhờ vậy ta cập nhật tại chỗ (in-place) trên một mảng duy nhất, đọc ghi đúng đắn không cần mảng hai chiều.

Ví dụ chạy tay

Lấy $N = 2$ nên có $4$ mask. Đặt mảng đầu vào (chỉ số theo nhị phân):

mask :  00   01   10   11
 a   :   1    2    3    4

Ta muốn $f [11] = a [00] + a [01] + a [10] + a [11] = 1 + 2 + 3 + 4 = 10$ , và $f [10] = a [00] + a [10] = 1 + 3 = 4$ , v.v.

Bước i = 0 (gộp theo bit 0): chỉ những mask có bit 0 = 1 (tức $01$ và $11$ ) mới cộng giá trị của mask đã tắt bit 0.

mask đang xét = 01 (bit0=1)  ->  f[01] += f[00]    : 2 + 1 = 3
mask đang xét = 11 (bit0=1)  ->  f[11] += f[10]    : 4 + 3 = 7

         00   01   10   11
trước :   1    2    3    4
sau   :   1    3    3    7
              ^^^       ^^^   (các ô được cập nhật)

Bước i = 1 (gộp theo bit 1): chỉ những mask có bit 1 = 1 (tức $10$ và $11$ ) mới cộng giá trị của mask đã tắt bit 1.

mask đang xét = 10 (bit1=1)  ->  f[10] += f[00]    : 3 + 1 = 4
mask đang xét = 11 (bit1=1)  ->  f[11] += f[01]    : 7 + 3 = 10

         00   01   10   11
trước :   1    3    3    7
sau   :   1    3    4   10
                   ^^^  ^^^   (các ô được cập nhật)

Kết quả cuối:

mask :  00   01   10   11
 f   :   1    3    4   10

Kiểm tra: $f [10] = 4 = a [00] + a [10]$ , $f [11] = 10$ = tổng tất cả. Đúng. Mỗi mask được "thu" thông tin từ mọi submask của nó chỉ qua 2 lượt cộng.

Cài đặt

Hàm chính — Subset Sum (zeta transform xuôi):

// f[mask] = tong cua a[sub] voi moi sub la submask cua mask
// n = so bit, a co kich thuoc 2^n
vector<long long> sos(vector<long long> a, int n) {
    vector<long long> f = a;            // tang i = 0: f[mask] = a[mask]

    for (int i = 0; i < n; i++)         // lan luot "mo khoa" tung bit
        for (int mask = 0; mask < (1 << n); mask++)
            if (mask >> i & 1)          // chi mask co bit i = 1 moi gop them
                f[mask] += f[mask ^ (1 << i)]; // cong submask da tat bit i

    return f;   // f[mask] = sum a[sub] voi sub ⊆ mask
}

Biến thể Superset Sum (tổng trên mọi mask chứa $m a s k$ ): chỉ cần đảo điều kiện bit và chiều cộng:

// g[mask] = sum a[sup] voi moi sup la superset cua mask (mask ⊆ sup)
vector<long long> superset_sum(vector<long long> a, int n) {
    vector<long long> g = a;
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < (1 << n); mask++)
            if (!((mask >> i) & 1))         // mask co bit i = 0
                g[mask] += g[mask | (1 << i)]; // cong superset da bat bit i
    return g;
}

Phép nghịch đảo (Möbius transform) khôi phục $a$ từ $f$ — dùng để "tháo" zeta sau khi nhân pointwise:

// Tu f[mask] = sum_{sub ⊆ mask} a[sub], khoi phuc a (Mobius nguoc cua zeta)
void mobius(vector<long long>& f, int n) {
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < (1 << n); mask++)
            if (mask >> i & 1)
                f[mask] -= f[mask ^ (1 << i)];  // doi dau so voi zeta
}

Ứng dụng tiêu biểu — AND convolution $c [k] = \sum_{i & j = k} a [i] \cdot b [j]$ :

// Y tuong: zeta theo SUPERSET hoa a, b ; nhan pointwise ; Mobius nguoc lai.
// (AND convolution dung superset-sum vi i & j = k <=> k la submask cua ca i va j)
void and_convolution(vector<long long>& a, vector<long long>& b,
                     vector<long long>& c, int n) {
    auto zeta_sup = [&](vector<long long>& f) {
        for (int i = 0; i < n; i++)
            for (int mask = 0; mask < (1 << n); mask++)
                if (!(mask >> i & 1)) f[mask] += f[mask | (1 << i)];
    };
    auto mobius_sup = [&](vector<long long>& f) {
        for (int i = 0; i < n; i++)
            for (int mask = 0; mask < (1 << n); mask++)
                if (!(mask >> i & 1)) f[mask] -= f[mask | (1 << i)];
    };
    zeta_sup(a); zeta_sup(b);
    c.assign(1 << n, 0);
    for (int mask = 0; mask < (1 << n); mask++) c[mask] = a[mask] * b[mask];
    mobius_sup(c);
}

Với XOR convolution ta dùng Walsh–Hadamard Transform (WHT) — cấu trúc lặp tương tự nhưng tổ hợp khác (cộng/trừ):

void wht(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int len = 1; len < n; len <<= 1)
        for (int i = 0; i < n; i += len << 1)
            for (int j = 0; j < len; j++) {
                long long u = a[i + j], v = a[i + j + len];
                a[i + j] = u + v;          // tong
                a[i + j + len] = u - v;    // hieu
            }
    if (inv) for (auto& x : a) x /= n;     // chuan hoa khi bien doi nguoc
}

Độ phức tạp

Thời gian: $O (N \cdot 2^{N})$ . Có $N$ vòng bit, mỗi vòng quét đủ $2^{N}$ mask và làm $O (1)$ việc. So với $O (3^{N})$ của cách duyệt submask trực tiếp, đây là bước nhảy lớn: với $N = 20$ thì $N \cdot 2^{N} \approx 2.1 \times 10^{7}$ thay vì $3^{20} \approx 3.5 \times 10^{9}$ .
Bộ nhớ: $O (2^{N})$ . Chỉ cần một mảng kích thước $2^{N}$ vì toàn bộ phép biến đổi làm tại chỗ — không cần mảng hai chiều $d p [N] [2^{N}]$ . Với $N = 20$ và kiểu long long, đó là khoảng $8 MB$ .

Bài toán	Cách ngây thơ	SOS DP
Tổng trên submask (một mask)	$O (2^{N})$	—
Tổng trên submask (mọi mask)	$O (3^{N})$	$O (N \cdot 2^{N})$
AND/OR/XOR convolution	$O (4^{N})$	$O (N \cdot 2^{N})$

⚠️ Lỗi thường gặp

Tràn số. Tổng trên submask cộng dồn rất nhiều giá trị; nếu $a [s u b]$ lớn hoặc nhiều, kết quả dễ vượt int. Luôn dùng long long, hoặc lấy modulo nếu đề yêu cầu. Khi có modulo, nhớ rằng phép Möbius có phép trừ — phải += MOD rồi %= MOD để tránh số âm.
Sai chiều quét / sai điều kiện bit. Subset-sum dùng if (mask >> i & 1) và cộng f[mask ^ (1<<i)]; superset-sum dùng if (!(mask >> i & 1)) và cộng f[mask | (1<<i)]. Lẫn lộn hai cái sẽ cho kết quả sai mà code vẫn chạy bình thường (không crash) — rất khó phát hiện. Hãy nhớ: subset thì tắt bit để cộng, superset thì bật bit để cộng.
Đảo thứ tự hai vòng lặp. Vòng ngoài phải là bit $i$ , vòng trong là $m a s k$ . Nếu để ngược (vòng ngoài là mask, trong là bit) thì một mask sẽ "ăn" giá trị đã được cập nhật một phần ở các bit thấp, gây cộng trùng (đếm một submask nhiều lần). Đây là lỗi kinh điển nhất.
Kích thước mảng không phải lũy thừa 2. Mảng phải có đúng $2^{N}$ phần tử và mọi mask thiếu (giá trị 0) vẫn phải tồn tại. Nếu chỉ cấp phát tới giá trị lớn nhất thực sự xuất hiện, f[mask ^ (1<<i)] sẽ truy cập ngoài biên.
Quên khởi tạo $f = a$ . Biến đổi làm tại chỗ trên bản sao của $a$ ; nếu khởi tạo $f$ bằng 0 rồi mới cộng thì mất hẳn số hạng $s u b = m a s k$ .
Chọn sai $N$ (số bit). $N$ phải đủ lớn để phủ giá trị lớn nhất ( $N \geq ⌈ \log_{2} (max + 1) ⌉$ ). Lấy $N$ thiếu một bit sẽ bỏ sót nửa số mask.

Biến thể / Mở rộng

Superset Sum & Möbius: đối ngẫu của subset-sum, đảo điều kiện bit và chiều cộng (xem code trên).
AND / OR / XOR convolution: OR convolution dùng subset-sum, AND dùng superset-sum, XOR dùng WHT — tất cả đều $O (N \cdot 2^{N})$ .
Đếm theo bao hàm – loại trừ: kết hợp SOS với inclusion–exclusion để đếm số tập con có AND/OR bằng một giá trị cho trước.
Liên hệ với kỹ thuật bitmask DP tổng quát: xem trang DP trên bitmask.

Bài tập luyện

Bài toán SOS Bitwise (sosbits) — (Veteran) Đếm với mỗi $x$ số phần tử là submask, superset, hay giao khác 0 — ứng dụng trực tiếp cả subset-sum lẫn superset-sum.
Đếm Tập Con AND (andsubcnt) — (Expert) Đếm số tập con có AND bằng $k$ cho mọi $k$ , giải bằng superset-sum SOS kết hợp Möbius/bao hàm–loại trừ.
Sắc Lệnh Giáo Dục (decree) — (Veteran) Bài bitmask + liệt kê tập con nâng cao được gắn tag sos_dp, luyện kết hợp SOS với DP trên trạng thái mặt nạ.