Tổng trên tập con (SOS DP)

Hướng tiếp cận

Yêu cầu là tính, với mỗi mask $m$, tổng $g[m]={\sum }_{s\subseteq m}f[s]$. Đây là dạng "Sum Over Subsets" (SOS) cổ điển.

Cách duyệt trực tiếp tốn $O(3^N)$ (mỗi bit có 3 lựa chọn: không thuộc $m$, thuộc $m$ và thuộc $s$, thuộc $m$ nhưng không thuộc $s$). Với $N=20$, $3^{20}\approx 3.5·{10}^9$ phép cộng — không khả thi trong 2 giây.

Nhận xét quan trọng

SOS DP biến đổi bài toán thành chuỗi $N$ phép quét, mỗi phép quét xử lý đúng một chiều bit. Sau khi xử lý xong bit $i$, giá trị $g[m]$ tạm thời là tổng của $f[s]$ trên mọi tập con $s$ của $m$ mà $s$ và $m$ trùng nhau ở các bit $>i$. Cuối cùng, sau $N$ vòng, $g[m]$ chính là tổng cần tìm.

Công thức truy hồi cho từng bit $i$:

• Nếu bit $i$ của $m$ bằng $0$: $g[m]$ không đổi.
• Nếu bit $i$ của $m$ bằng $1$: (cộng thêm phần đóng góp khi bit $i$ của $s$ bằng $0$).

Thuật toán

g[m] = f[m]  với mọi m
for i in 0 .. N-1:
    for m in 0 .. 2^N - 1:
        if m & (1 << i):
            g[m] += g[m ^ (1 << i)]

Thứ tự vòng lặp rất quan trọng: bit $i$ phải nằm vòng ngoài, mask $m$ vòng trong. Nếu đảo lại ($m$ ngoài, $i$ trong) thì kết quả sẽ sai vì khi đến bit $i$, các giá trị $g[m\oplus (1\ll i)]$ chưa đầy đủ qua các bit còn lại.

Lưu ý kiểu dữ liệu: $|g[m]|$ có thể tới $2^{20}·{10}^9\approx {10}^{15}$, dùng long long trong C++.

Độ phức tạp

• Thời gian: $O(N·2^N)\approx 2·{10}^7$ phép cộng khi $N=20$.
• Bộ nhớ: $O(2^N)$ số 64-bit, khoảng 8 MB.