SOS DP (Sum over Subsets)

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

huunguyen · Last updated 8, Tháng 4, 2026, 16:02

SOS DP (Sum over Subsets) tính $f [m a s k] = \sum_{s u b \subseteq m a s k} a [s u b]$ cho tất cả mask trong $O (N \cdot 2^{N})$ thay vì $O (3^{N})$ (duyệt mọi cặp mask-submask).

Ý tưởng

Thay vì duyệt mọi submask của mask, xử lý từng bit một:

d p [m a s k] [i] = \sum_{sub \subseteq m a s k, sub chỉ khác mask ở bit \geq i} a [s u b]

Chuyển tiếp:

Nếu bit $i$ của mask = 0: $d p [m a s k] [i] = d p [m a s k] [i + 1]$ (không có submask mới từ bit này).
Nếu bit $i$ của mask = 1: $d p [m a s k] [i] = d p [m a s k] [i + 1] + d p [m a s k \oplus (1 < < i)] [i + 1]$ .

Cài đặt

// f[mask] = sum của a[sub] với mọi sub là subset của mask
vector<long long> sos(vector<long long>& a, int n) {
    // n = số bit, a có kích thước 2^n
    vector<long long> f = a;

    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)];

    return f;   // f[mask] = sum a[sub] với sub ⊆ mask
}

Giải thích: Sau vòng lặp bit $i$ , f[mask] chứa tổng của tất cả subset của mask chỉ xét các bit từ $0$ đến $i$ .

Superset Sum

Tính $g [m a s k] = \sum_{m a s k \subseteq s u p} a [s u p]$ (tổng trên superset):

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 = (1<<n)-1; mask >= 0; mask--)
            if (!((mask >> i) & 1))
                g[mask] += g[mask | (1 << i)];
    return g;
}

Ứng dụng 1: AND Convolution

Tính $c [k] = \sum_{i & j = k} a [i] \cdot b [j]$ cho mọi $k$ :

// Dùng AND convolution (zeta/Mobius transform)
// Bước 1: f_a[mask] = sum a[sub] với sub ⊆ mask
// Bước 2: f_c = f_a * f_b (pointwise)
// Bước 3: Möbius inversion để lấy c

void and_convolution(vector<long long>& a, vector<long long>& b,
                     vector<long long>& c, int n) {
    auto zeta = [&](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 = [&](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(a); zeta(b);
    c.resize(1<<n);
    for (int mask = 0; mask < (1<<n); mask++) c[mask] = a[mask] * b[mask];
    mobius(c);
}

Ứng dụng 2: OR Convolution (OR Transform)

$c [k] = \sum_{i | j = k} a [i] \cdot b [j]$ — tương tự nhưng dùng superset sum.

Ứng dụng 3: XOR Convolution

$c [k] = \sum_{i \oplus j = k} a [i] \cdot b [j]$ — dùng Walsh-Hadamard Transform (WHT).

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; a[i+j+len] = u - v;
            }
    if (inv) for (auto& x : a) x /= n;
}

void xor_convolution(vector<long long>& a, vector<long long>& b, vector<long long>& c) {
    wht(a, false); wht(b, false);
    c.resize(a.size());
    for (int i = 0; i < (int)a.size(); i++) c[i] = a[i] * b[i];
    wht(c, true);
}

Độ phức tạp

Bài toán	Brute Force	SOS DP
Sum over subsets (1 mask)	$O (2^{N})$	—
Sum over subsets (tất cả mask)	$O (3^{N})$	$O (N \cdot 2^{N})$
AND/OR/XOR convolution	$O (4^{N})$	$O (N \cdot 2^{N})$

Khi nào dùng SOS DP?

Tính tổng trên tất cả submask của mọi mask ( $N \leq 20$ ).
AND/OR/XOR convolution (nhân đa thức trên vành $({0, 1}^{N}, &)$ , v.v.).
Bài toán bitmask DP cần "tổng hợp thông tin từ tất cả trạng thái con".

Bình luận

Không có bình luận tại thời điểm này.