Tổng trên tập con (Sum over Subsets) - Dynamic Programming trong C++

Giới thiệu

Cho mảng A kích thước 2ⁿ. Tính F(x) = Σ A[i] với mọi i là tập con bitwise của x (i & x == i). Áp dụng DP trên bitmask (SOS DP).

Ví dụ

A = [5, 7, 1, 9], n = 2 (kích thước 4 = 2²)

x = 0 (00): i ∈ {00} → F(0) = A[0] = 5

x = 1 (01): i ∈ {00, 01} → F(1) = A[0] + A[1] = 12

x = 2 (10): i ∈ {00, 10} → F(2) = A[0] + A[2] = 6

x = 3 (11): i ∈ {00, 01, 10, 11} → F(3) = 5+7+1+9 = 22

Thuật toán SOS DP

DP[mask][i] = tổng các A[sub] với sub ⊆ mask và sub chỉ khác mask ở các bit > i

Công thức truy hồi:

• Bit i của mask = 1: DP[mask][i] = DP[mask][i-1] + DP[mask^(1<<i)][i-1]
• Bit i của mask = 0: DP[mask][i] = DP[mask][i-1]

Mã nguồn hoàn chỉnh

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

void sumOverSubsets(vector &a, int n) {
    int N = 1 << n;
    vector dp(N);
    
    // Khởi tạo: dp[mask] = a[mask]
    for (int mask = 0; mask < N; mask++) {
        dp[mask] = a[mask];
    }
    
    // SOS DP
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < N; mask++) {
            if (mask & (1 << i)) {
                dp[mask] += dp[mask ^ (1 << i)];
            }
        }
    }
    
    // In kết quả
    for (int mask = 0; mask < N; mask++) {
        cout << dp[mask] << " ";
    }
    cout << endl;
}

int main() {
    vector A = {5, 7, 1, 9};
    int n = 2;
    
    cout << "Sum over subsets: ";
    sumOverSubsets(A, n);
    
    return 0;
}

Kết quả chạy chương trình

Sum over subsets: 5 12 6 22

Phân tích độ phức tạp

• Thời gian: O(n × 2ⁿ)
• Không gian: O(2ⁿ)

So sánh với brute force

Biến thể: Sum over Supersets

Tính F(x) = Σ A[i] với x ⊆ i (x là tập con của i):

for (int i = 0; i < n; i++) {
    for (int mask = 0; mask < N; mask++) {
        if (!(mask & (1 << i))) {
            dp[mask] += dp[mask | (1 << i)];
        }
    }
}

Ứng dụng

• Tính số lượng tập con thỏa mãn điều kiện
• Xử lý truy vấn trên tập hợp (subset queries)
• Bài toán vali, knapsack trên bitmask
• Fast Zeta Transform / Möbius Transform

Kết luận

SOS DP (Sum Over Subsets DP) là kỹ thuật cơ bản trong competitive programming cho bài toán bitmask. Độ phức tạp O(n2ⁿ) tối ưu cho n ≤ 20.