Editorial: Mathematical Algorithms TWK Open Problem #D - Tam Phân Tập Hợp

1.Ý tưởng

Bài toán yêu cầu tính tổng \(B[S] = \sum A[S_1] \cdot A[S_2] \cdot A[S_3]\) với mọi bộ ba tập rời nhau từng đôi một \((S_1, S_2, S_3)\) sao cho \(S_1 \cup S_2 \cup S_3 = S\).

Đây chính là phép chập tập con (Subset Convolution) áp dụng 3 lần liên tiếp:
\(B = A * A * A\)

1. Bản chất của Subset Convolution:
2. Phép chập OR thông thường (SOS DP / Fast Mobius Transform) tính \(\sum_{X \cup Y = S} F[X] \cdot G[Y]\).

3. Để đảm bảo điều kiện hai tập rời nhau (\(X \cap Y = \varnothing\)), ta tận dụng tính chất độ lớn tập hợp:
   \(X \cap Y = \varnothing \iff |X| + |Y| = |X \cup Y| = |S|\) (với \(|S| = \text{popcount}(S)\)).

4. Thuật toán:

5. Bước 1 (Phân loại theo Rank/Popcount): Mở rộng mảng \(A\) thành mảng 2D \(f[k][mask]\) trong đó \(f[k][mask] = A[mask]\) nếu \(\text{popcount}(mask) == k\), ngược lại bằng \(0\).
6. Bước 2 (FMT / SOS DP): Với mỗi tầng \(k \in [0, n]\), áp dụng biến đổi Fast Mobius Transform trên các bit mask.
7. Bước 3 (Nhân điểm đa thức): Tại mỗi mask, mảng \(f[0\dots n][mask]\) đóng vai trò là hệ số của một đa thức bậc \(n\). Ta tiến hành nhân đa thức này \(3\) lần (\(f \cdot f \cdot f\)) với quy tắc nhân chập thông thường (Convolution) để thu được đa thức kết quả \(h[0\dots n][mask]\).
8. Bước 4 (IFMT / Inverse SOS DP): Thực hiện biến đổi ngược Inverse Fast Mobius Transform cho từng tầng \(k\).
9. Bước 5 (Trích xuất kết quả): Giá trị \(B[S]\) chính là \(f[\text{popcount}(S)][S]\).

2.Độ phức tạp

• Thời gian:
• Phân loại & SOS DP: \(O(n^2 \cdot 2^n)\).
• Nhân đa thức tại mỗi mask: \(O(2^n \cdot n^2)\).
• Inverse SOS DP: \(O(n^2 \cdot 2^n)\).
• Tổng thời gian: \(O(n^2 \cdot 2^n)\).
• Không gian bộ nhớ: \(O(n \cdot 2^n)\) để lưu mảng bảng SOS DP.