# Sum over Subset DP và các bài toán liên quan

|[TOC]|
|---|

# Giới thiệu

**Sum over Subset DP (SoS DP)** là một kỹ thuật quy hoạch động bitmask.

# Lưu ý trước khi đọc bài viết

Trước khi đọc blog này, bạn đọc nên nắm chắc về quy hoạch động bitmask cũng như các phép toán trên bit. Bạn có thể đọc bài viết **[Phép toán bit](https://wiki.vnoi.info/vi/algo/basic/bitwise-operators)** để biết thêm về chủ đề này.

Các khái niệm được sử dụng trong bài viết:

* Biểu diễn nhị phân trong bài toán được đánh số từ $0$, các bit viết từ **trái sang phải** theo thứ tự từ **bit nhỏ đến bit lớn**. Ví dụ: $1101_2 = 11_{10}$, gồm có bit thứ $0$ là $1$, bit thứ $1$ là $1$, bit thứ $2$ là $0$, bit thứ $3$ là $1$.
* Dấu $\&$ là toán tử bitwise AND.
* Dấu $\oplus$ là toán tử bitwise XOR.
* Dấu $|$ là toán tử bitwise OR.
* $\text{popcount}(x)$ là số bit có giá trị là $1$ của $x$.
* Một số $a$ là tập con của $b$ nếu trong biểu diễn nhị phân của $a$ ở các vị trí có giá trị là $1$ thì ở vị trí đó của $b$ giá trị cũng là $1$. Nói cách khác, $a$ là tập con của $b$ khi $a\&b=a$.
* Ta định nghĩa $a \subseteq b$ nghĩa là $a$ là tập con của $b$.

# Bài toán

## Đề bài

Cho một mảng $A$ gồm $2^N$ phần tử, ta định nghĩa hàm $F(mask)$ là tổng của mọi $A[i]$ sao cho $i$ là tập con của $mask$, hay $F(mask) = \sum_{i \subseteq mask}A[i]$.

Tính $F(mask) \; \forall \; 0 \leq mask < 2^N$.

Giới hạn: $0 \leq A[i] \leq 10^9$, $N \leq 20$

## Lời giải

### Cách giải ngây thơ

Ta duyệt qua mọi $mask$ và $i$ rồi kiểm tra như định nghĩa và tính.

for(int mask = 0; mask < (1<<N); mask++){
    for(int i = 0; i < (1<<N); i++){
        if((mask&i) == i){
            F[mask] += A[i];
        }
    }
}

Cách tính này có độ phức tạp là $O(4^N)$.

#### Tối ưu cách giải ngây thơ

Ta sử dụng kĩ thuật duyệt qua mọi tập con được nhắc đến trong blog **[Phép toán bit](https://wiki.vnoi.info/vi/algo/basic/bitwise-operators)**.

for (int mask = 0; mask < (1<<N); mask++){
    F[mask] = A[0];
    for(int i = mask; i > 0; i = (i-1) & mask){
    	F[mask] += A[i];
    }
}

Cách duyệt này có độ phức tạp $O(3^N)$. Phần chứng minh độ phức tạp đã có trong bài viết trên.

### Cách giải quy hoạch động

Ta cần tìm cách duyệt và tính tổng các tập con nhanh hơn. Nhận thấy rằng ở cách giải trên, mỗi số có $K$ bit bằng $0$ được duyệt qua $2^K$ lần, nghĩa là ta đang tính lại rất nhiều.

Ta cần tìm một cách tính sử dụng mối quan hệ giữa các phần tử $A[i]$ nằm trong nhiều $F(mask)$ khác nhau và cần một trạng thái quy hoạch có thể chia từng số vào các nhóm khác nhau để tránh bị tính trùng.

Ta định nghĩa $S(mask) = \{x|x \subseteq mask\}$. Ta sẽ tìm cách chia tập này thành các tập không giao nhau. Ta định nghĩa $S(mask, i) = \{x|x \subseteq mask \; \&\& \; x \oplus mask < 2^i\}$, hay $S(mask, i)$ là tập các số sao cho mỗi số là tập con của $mask$ và chỉ khác $mask$ trong $i$ bit đầu. Lưu ý $i$ bit đầu là bao gồm các bit từ bit thứ $0$ đến bit thứ $i-1$.

Ví dụ: $S(101\color{red}{001}, 3) = \{{000\color{red}{001}, 001\color{red}{001}, 100\color{red}{001}, 101\color{red}{001}}\}$, $S(\color{red}{1101}, 0) = \{\color{red}{1101}\}$, $S(1010, 4) = \{0000, 0010, 1000, 1010\}$. Phần được bôi đỏ là phần không được khác với $mask$.

Ta có thể thấy $S(mask, 0) = \{mask\}$ và $S(mask, N) = S(mask)$.

Ta cần tìm mối quan hệ giữa các $S(mask, i)$. Xét bit thứ $i-1$ của $mask$:

* Nếu bit thứ $i-1$ của $mask$ là $0$, tất cả các phần tử trong $S(mask, i)$ đều có bit thứ $i-1$ là $0$. Do đó, tất cả các phần tử chỉ khác với $mask$ trong $i-1$ bit đầu tiên. Ta suy ra $S(mask, i) = S(mask, i-1)$.

* Nếu bit thứ $i-1$ của $mask$ là $1$, ta chia được tập $S(mask, i)$ thành 2 tập không giao nhau. Phần thứ nhất gồm các phần tử có bit thứ $i-1$ là $1$, các phần tử này chỉ khác với $mask$ trong $i-1$ bit đầu, tương đương với $S(mask, i-1)$. Còn phần thứ 2 gồm các phần tử có bit thứ $i-1$ bằng $0$ chỉ khác với $mask \oplus 2^{i-1}$ trong $i-1$ bit đầu nên phần này tương đương với $S(mask \oplus 2^{i-1}, i-1)$

Như vậy ta có:

$$
S(mask, i)=
\begin{cases}
S(mask, i-1) &\style{font-family:Cambria Math}{\text{ nếu bit thứ }} i-1 \text{ là } 1 \\
S(mask, i-1) \cup S(mask \oplus 2^{i-1}, i-1) &\style{font-family:Cambria Math}{\text{ nếu bit thứ }} i-1 \text{ là } 0
\end{cases}
$$

Với trạng thái ban đầu là $S(mask, 0) = \{mask\}$

#### Code

for(int i = 0; i <= N; i++){
    for(int mask = 0; mask < (1<<N); mask++){
        if(i == 0)F[mask][i] = A[mask];
        else {
            if(mask&(1<<(i-1)))F[mask][i] = F[mask][i-1] + F[mask^(1<<(i-1))][i-1];
            else F[mask][i] = F[mask][i-1];
        }
    }
}

Rút gọn code và tối ưu bộ nhớ:

for(int i = 0; i < (1<<N); i++)
	F[i] = A[i];
for(int i = 1; i <= N; i++)
    for(int mask = 0; mask < (1<<N); mask++)
        if(mask & (1<<i)) F[mask] += F[mask^(1<<i)];

Bạn có thể thấy thuật toán này vô cùng dễ nhớ. Độ phức tạp của thuật toán là $O(2^N \times N)$

Nếu chưa rõ về cách chuyển trạng thái, có thể nhìn hình minh họa cho tập $S(1011, 4)$. Trong hình dưới đây, phần màu đỏ của một đỉnh là các bit mà tất cả các đỉnh trong cây con gốc là đỉnh đó đều giống nhau.

Nếu vẽ toàn bộ các trạng thái tập, các trạng thái sẽ tạo thành một đồ thị có hướng không có chu trình.

# Các bài toán liên quan

## Bài toán ngược

### Đề bài

Cho mảng $F$ gồm $2^N$ phần tử. Tìm mảng $A$ gồm $2^N$ phần tử sao cho $F[x] = \sum_{i \subseteq x} A[i]$.

Giới hạn: $0 \leq F[i] \leq 10^9$, $N \leq 20$

### Lời giải 1

Ta thực hiện chính xác ngược lại các bước khi tính SOS DP. Cài đặt rất ngắn và dễ nhớ.

### Code mẫu 1

void SOS_DP_reverse(long long F[], int N){ // Hàm nhận mảng F độ dài 2^N, biến đổi trực tiếp trên mảng F sao cho mảng SOS của F mới là F cũ.
    for(int i = N-1; i >= 0; i--){
        for(int mask = (1<<N) - 1; mask >= 0; mask--){
            if(F[mask] & (1<<i))F[mask] -= F[mask ^ (1<<i)];
        }
    }
    // Mảng F giờ chứa kết quả
}

### Lời giải 2

Ta sẽ sử dụng kĩ thuật bao hàm loại trừ. Ta có:

$$
A[x] = \sum_{i \subseteq x} F[i] \times (-1)^{
\text{popcount}(x \oplus i)
}
$$

Nói cách khác, $A[x]$ bằng tổng $F[i]$ sao cho $i$ là tập con khác **chẵn** bit của $x$ trừ đi tổng $F[i]$ sao cho $i$ là tập con khác **lẻ** bit của $x$. Nếu không rõ tại sao có công thức này, bạn có thể đọc thêm về **[Bao hàm loại trừ](https://wiki.vnoi.info/vi/translate/he/Number-Theory-7)**.

Ta biến đổi thành:

$$
\begin{aligned}
A[x] &= \sum_{i \subseteq x} F[i] \times (-1)^{
\text{popcount}(i)} \times (-1)^{\text{popcount}(x)}\\
\Rightarrow \; A[x] &= (-1)^{\text{popcount}(x)} \times \sum_{i \subseteq x} F[i] \times (-1)^{
\text{popcount}(i)}
\end{aligned}
$$

Như vậy ta chỉ cần đổi dấu các $F[i]$ có $\text{popcount}(x)$ lẻ rồi thực hiện SoS DP là được

### Code mẫu 2

void SOS_DP(long long A[], int N){ // hàm nhận mảng A độ dài 2^N, biến đổi mảng A thành mảng SOS của A
    for(int i = 0; i < N; i++){
        for(int mask = 0; mask < (1<<N); mask++){
            if(A[mask] & (1<<i))A[mask] += A[mask ^ (1<<i)];
        }
    }
}

void SOS_DP_reverse(long long F[], int N) {
    for(int i = 0; i < (1<<N); i++){
        if(__builtin_popcount(i) & 1)F[i] = F[i]*-1;
    }
    SOS_DP(F, N);
    for(int i = 0; i < (1<<N); i++){
        if(__builtin_popcount(i) & 1)F[i] = F[i]*-1;
    }
    // Mảng F giờ chứa kết quả
}

## AND/OR convolution

### Đề bài

Cho mảng $A$ và $B$ độ dài $2^N$, với mọi $i$ từ $0$ đến $2^N - 1$, tính $C[i] = \sum_{j|k = i}A[j]\times B[k]$

Giới hạn: $0 \leq A[i], B[i] \leq 10^9$, $N \leq 20$

### Lời giải

Ta gọi $A'[i] = \sum_{d\subseteq i}A[d]$, $B'[i] = \sum_{d\subseteq i}B[d]$.

Để tính được $C[i]$, ta tính $C'[i] = \sum_{d\subseteq i}C[d]$ trước, rồi tính $C[i]$ bằng bài toán ngược như trên.

Ta có:

$$
\begin{aligned}
C'[i]
&=\sum_{d\subseteq i}C[d] \\
&=\sum_{d \subseteq i}\sum_{j|k = d}A[j] \times B[k] \\
&=\sum_{j|k \subseteq i}A[j] \times B[k] \\
\end{aligned}
$$

Nhận thấy $j|k \subseteq i$ khi và chỉ khi $j \subseteq i$ và $k \subseteq i$. Ta biến đổi được như sau:

$$
\begin{aligned}
C'[i]
&= \sum_{j \subseteq i, k \subseteq i}A[j] \times B[k] \\
&=\left( \sum_{j\subseteq i}A[j] \right) \times \left(\sum_{k\subseteq i}B[k] \right)\\
&= A'[i] \times B'[i]
\end{aligned}
$$

Đến đây, ta thực hiện SoS DP trên 2 mảng $A$ và $B$, nhân 2 mảng với nhau rồi thực hiện bài toán ngược là xong.

### Code mẫu

void SOS_DP(long long A[], int N){
    for(int i = 0; i < N; i++){
        for(int mask = 0; mask < (1<<N); mask++){
            if(A[mask] & (1<<i))A[mask] += A[mask ^ (1<<i)];
        }
    }
}

void SOS_DP_reverse(long long A[], int N){ 
    for(int i = N-1; i >= 0; i--){
        for(int mask = (1<<N) - 1; mask >= 0; mask--){
            if(A[mask] & (1<<i))A[mask] -= A[mask ^ (1<<i)];
        }
    }
}

void solve(long long A[], long long B[], int N) {
    SOS_DP(A, N);
    SOS_DP(B, N);
    for(int i = 0; i < (1<<N); i++){
        A[i] *= B[i];
    }
    SOS_DP_reverse(A, N);
    // Mảng A giờ chứa kết quả
}

### AND convolution

Nếu ta xor mọi số $i$ với $2^N - 1$, AND convolution tương đương với OR convolution nên ta cũng giải như trên.

# Bài tập tham khảo

* [Codeforces - Compatible Numbers](https://codeforces.com/contest/165/problem/E)
* [Codeforces - Vowels](https://codeforces.com/contest/383/problem/E)
* [Codechef - Covering Sets](https://www.codechef.com/SNFL16MR/problems/BEAUTY)
* [HackerRank - Vim War](https://www.hackerrank.com/contests/countercode/challenges/subset)
* [Codeforces - Jzzhu and Numbers](https://codeforces.com/problemset/problem/449/D)
* [Codechef - Strange Funtions](https://www.codechef.com/problems/STR_FUNC)
* [Library Checker - Biwise And Convolution](https://judge.yosupo.jp/problem/bitwise_and_convolution)