$\text{🌱 DP SOS Tutorial}$

---

🔗 Link:
📌 Tags: DP Bitmask Tutorial
✍🏻 Writer: @SPyofgame
🔎 Editor:
⚒️ Contributor: @ngpin04
📋 Content:

• A. Giới thiệu
• B. Phát biểu bài toán
• C. Trâu hết toàn bộ trạng thái
• D. Duyệt qua tập trạng thái con
  • 1) Ý tưởng
  • 2) Cài đặt
  • 3) Độ phức tạp
  • 4) Tính đúng đắn
• E. Quy hoạch động tổng tập con
  • 1) Ý tưởng
  • 2) Tiếp cận
  • 3) Cài đặt
• F. Ứng dụng
  • 1) Dạng bài liên quan
  • 2) Dạng bài thường gặp
  • 3) Bài tập để luyện
• Z. Phản hồi từ người đọc

---

A. Giới thiệu

Quy hoạch động tổng tập con, hay DP SOS, là một chủ đề khá mới nhưng đang dần phổ biến trong kỳ thi học sinh giỏi quốc gia môn tin học khi lần đầu được xuất hiện ở bài 3 kỳ VOI 2020.

---

B. Phát biểu bài toán

Cho một mảng

$a[i]$ gồm các phần tử nguyên ta cần tính được mảng

$F[mask]=\underset{sub\subseteq mask}{\mathrm{\Sigma }}a[sub]$ .

---

C. Trâu hết toàn bộ trạng thái

Với một tư tưởng đơn giản, ta chỉ cần duyệt qua các

$mask$, và với mỗi

$mask$ ta sẽ xét qua các tập con

$submask\subseteq mask$ trên mảng

$a[0.{.2}^n-1]$ để cập nhật kết quả

$f[mask]$. Cụ thể là:

Brute-force

Brute-force

👤Author: @SPyofgame
🏷️Code Tag: Bruteforces
💡Comment: Cách cài đặt bằng vòng lặp trên mọi tập trạng thái.
⏳Time Complexity:

$O(4^n)$
💾Space Complexity:

$O(2^n)$

/// Duyet qua cac trang thai mask
for (int mask = 0; mask < (1 << n); ++mask) /// O(2^n)
{
    /// Tinh F[mask] = Sigma(submask) a[submask]
    /// Bai toan khong can tinh a[0] thi gan submask = 1
    for (int submask = 0; submask < (1 << n); ++submask) /// O(2^n)
    {
        if ((mask & submask) == submask)
        {
            F[mask] += a[submask];
        }
    }
}

:::

Với ý tưởng cài cơ bản như vậy, ta đạt được độ phức tạp

$O(2^n)\times O(2^n)\subseteq O(4^n)$ thời gian và

$O(2^n)$ bộ nhớ.

---

D. Duyệt qua tập trạng thái con

1) Ý tưởng

Tất nhiên ta nhận xét là không phải trạng thái nào cũng đáng để duyệt.

Mình chỉ cần quan tâm các

$submask\in mask$ mà cập nhật vào

$F[mask]$.

Với mỗi

$mask$ ta duyệt, ta sẽ xét qua các

$submask$ bằng cách duyệt tập con của

$mask$.

2) Cài đặt

Submask Enumeration

👤Author: @SPyofgame
🏷️Code Tag: Submask Enumeration
💡Comment: Cách cài đặt bằng vòng lặp trên các trạng thái cần thiết.
⏳Time Complexity:

$O(3^n)$
💾Space Complexity:

$O(2^n)$

/// Duyet qua cac mask
for (int mask = 0; mask < (1 << n); ++mask) /// O(2^n)
{
    /// Tinh F[mask] = Sigma(submask) a[submask]
    F[mask] = a[0]; /// Xoa neu bai toan khong can xet TH [x = 0]
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) /// O(2^|mask|) 
    {
        F[mask] += a[mask]; /// submask chac chan la con cua mask
    }
}

3) Độ phức tạp

Nhìn chung có vẻ chỉ giảm hằng số bằng cách lọc các trường hợp rác, nhưng thực ra độ phức tạp thời gian cũng giảm theo, đó là:

$\underset{mask\subseteq S}{\stackrel{}{\mathrm{\Sigma }}}\left(2^{|mask|}\right)=\underset{k=0}{\stackrel{n}{\mathrm{\Sigma }}}\underset{mask\subseteq S}{\stackrel{}{\mathrm{\Sigma }}}\left(\left[|mask|=k\right]\times 2^k\right)=\underset{k=0}{\stackrel{n}{\mathrm{\Sigma }}}(\genfrac{}{}{0ex}{}{n}{k})\times 2^k=(1+2{)}^n=3^n$
*Ở đây

$S$ là tập các trạng thái cần xét, cụ thể là

$S=\{0,1,2,\dots ,2^n-1\}$.
*Ở đây hàm

$\left[x=y\right]$ trả về

$1$ khi biểu thức

$(x=y)$ đúng và trả về

$0$ với trường hợp ngược lại.
*Ở đây hàm

$|mask|$ trả về số bit

$1$ trong tập trạng thái

$mask$.

Hay nói một cách đơn giản và dễ hiểu hơn thì, tại mỗi vị trí bit trên tập trạng thái

$mask[i]$ chỉ có

$3$ trường hợp độc lập nhau, nên số cách tạo ra với

$n=|mask|$ vị trí như vậy là

$O(3^n)$. Cụ thể các trường hợp đó là:

$mask[i]=1$ và

$submask[i]=1$

$mask[i]=1$ và

$submask[i]=0$

$mask[i]=0$ và

$submask[i]=0$
*Lưu ý trường hợp

$mask[i]=0$ thì mọi tập trạng thái

$S$ có

$S[i]=1$ đều là

$S\notin mask$.

4) Tính đúng đắn

Toàn bộ quá trình lặp thì

$1\le submask\le mask$.

Nên ta không cần xét với trường hợp số âm thì nó sẽ làm gì,
Khi

$submask=0$ thì rõ ràng vòng lặp đã kết thúc hoặc/và trường hợp được xét riêng.

Gọi vị trí bit

$1$ cuối của

$(submask-1)$ là

$p$. Thì

$submask$ sẽ lật các bit

$0$ ở sau

$p$ thành

$1$ và lật bit

$p$ thành

$0$.

11110100 thành 11110011 (

$p=2$, Lật 2 bit cuối)
?0010010 thành ?0010001 (

$p=1$, Lật 1 bit cuối)
???10000 thành ???01111 (

$p=4$, Lật 4 bit cuối)
???????1 thành ???????0 (

$p=0$, ✦Tức là trong trường hợp bit cuối là

$1$ thì mệnh đề đúng).
Lưu ý

$p$ trên tập trạng thái

$mask$ được định nghĩa là đánh số từ bit

$0$.

Giá trị

$((submask-1)\mathrm{\&}mask)$ sẽ chỉ lấy những giá trị bit là tập con của

$mask$

Dễ dàng nhận xét được là giá trị

$p$ sẽ tăng dần và

$p=0$ đúng với mọi

$mask$ (từ ✦).
Gọi

$submask\in X(mask,k)$, với tập

$X(mask,k)$ chứa các

$submask$ sau khi thay đổi

$mask$ với

$k$ bit cuối.
Khi

$mask[k]=0$, thì

$mask$ không có thay đổi, hay nói cách khác là

$submask$ không được tạo ra tại vị trí

$p=k$ do đó

$X(mask,k)=X(mask,k-1)$
Khi

$mask[k]=1$ ta có các

$submask$ con được tạo ra là

$X(mask,k)=X(mask,k-1)+X(mask\oplus 2^{k-1},k-1)$

• Trong đó
  $X(mask,k-1)$ là khi tồn tại bit
  $1$ trong
  $k$ bit cuối, tức xét toàn bộ
  $submask$ của
  $mask$ trong
  $k-1$ vị trí cuối.
• Trong đó
  $X(mask\oplus 2^{k-1},k-1)$ là khi toàn bộ
  $k$ bit cuối là
  $0$, tức xét các toàn bộ
  $submask$ sau khi lật bit
  $mask[k]$.
• Nhắc lại, các bit trên tập trạng thái được mặc định là đánh số từ vị trí
  $0$, cẩn thận nhầm lẫn.

Vậy ta có điều phải chứng minh.

---

E. Quy hoạch động tổng tập con

1) Ý tưởng

Thay vì duyệt qua toàn bộ submask con để cập nhật kết quả, thì chẳng phải là

$F[mask]$ cũng phải có mối liên hệ gì đó với

$F[submask]$, do bọn nó lấy tổng dựa trên tập con à ?

Dễ thấy mỗi

$a[i]$ cập nhật lên các

$F[mask]$ và

$F[submask]$ nhiều lần.
Nếu

$m_0,m_1,\dots ,m_k$ là các tập con tách ra từ

$mask$, hay:

• $m_0\cap m_1\cap \dots \cap m_k=\mathrm{\varnothing }$
• $m_0\cup m_1\cup \dots \cup m_k=mask$

Cách đơn giản nhất để tạo mối liên hệ này đó chính là xét

$|m_i|\in \{0,1\}$

Khi

$|m_i|=0$ có nghĩa là ta cập nhật

$F[mask]$ nào đó mà có thêm

$submask[i]=0$.
Khi

$|m_i|=1$ có nghĩa là ta cập nhật

$F[mask]$ nào đó mà có thêm

$submask[i]=1$.

Tất nhiên ta không cần tới công thức bao hàm loại trừ:

$F[mask]=a[mask]-\underset{i_1=0}{\stackrel{k}{\mathrm{\Sigma }}}a[mask\setminus m_{i_1}]+\underset{0\le i_1<i_2}{\stackrel{k}{\mathrm{\Sigma }}}a[mask\setminus (m_{i_1}\cup m_{i_2})]-\underset{0\le i_1<i_2<i_3}{\stackrel{k}{\mathrm{\Sigma }}}a[mask\setminus (m_{i_1}\cup m_{i_2}\cup m_{i_3})]+\dots$
Hay

$F[mask]=a[mask]+\underset{p=0}{\stackrel{k}{\mathrm{\Sigma }}}$

Mà ta chỉ cần đơn giản hoá

$\{m_0,m_1,m_2,\dots ,m_k\}$ như sau

Ta đặt

$k=n-1$ và

$m_i=submask[i]$.

2) Tiếp cận

Nhắc lại, ta có quan hệ của

$submask$ với

$mask$ là

$mask[i]=1$ thì

$submask[i]\in \{0,1\}$

$mask[i]=0$ thì

$submask[i]=0$

Vậy ta có thể đưa bài toán về dạng quy hoạch động

$G[mask][-1]=a[mask]$.

$G[mask][i]$ là tổng tìm được, ứng với

$mask$ và xét

$[i]$ vị trí đầu tiên trong

$mask$.
Xét

$mask[i]=0$ và

$mask[i]=1$ để tìm công thức tương ứng với các

$submask$.

Khi ta xét

$mask[i]=0$

Không khó để suy ra được

$|m_i|=0\Rightarrow m_i=\mathrm{\varnothing }$.
Vì như trên ta đã nói, khi

$mask[i]=0$ thì

$submask[i]=0$, nên

$|m_i|\ne 1$.
Lúc này

$G[mask][i]=G[mask][i-1]$.

Khi ta xét

$mask[i]=1$

Trường hợp một, ta có

$m_i=\mathrm{\varnothing }$, có giá trị con là

$G[mask][i-1]$.
Trường hợp hai, ta có

$m_i=\{i\}$, có giá trị con là

$G[mask\setminus m_i][i-1]$.
Lúc này

$G[mask][i]=G[mask][i-1]+G[mask\setminus m_i][i-1]$.
Biểu diễn kiểu tin học là

$G[mask][i]=G[mask][i-1]+G[mask\oplus 2^i][i-1]$.

Công thức rút gọn như sau:

$G[mask][-1]=a[mask]$.

$G[mask][i]=G[mask][i-1]+mask[i]\times G[mask\oplus 2^i][i-1]$.

Độ phức tạp công thức

Độ phức tạp thời gian:

$O(2^n\times n)$.
Độ phức tạp bộ nhớ:

$O(2^n\times n)$.
Có thể duyệt

$i=[0,n)$ rồi mới duyệt

$mask\in [0,2^n)$ để giảm bộ nhớ còn

$O(2^n)$.

3) Cài đặt

Iterative DP SOS [1]

👤Author: @SPyofgame
🏷️Code Tag: DP SOS
💡Comment:

$G[mask][i]$ là tổng tìm được, ứng với

$mask$ và xét

$[i]$ vị trí đầu tiên trong

$mask$.
⏳Time Complexity:

$O(2^n\times n)$
💾Space Complexity:

$O(2^n\times n)$

/// Duyet qua cac mask
for(int mask = 0; mask < (1<<N); ++mask) /// O(2^n)
{
    G[mask][-1] = A[mask]; /// Base Case: co the bo neu bai toan khong yeu cau
    for (int i = 0; i < n; ++i) /// O(n)
    {
        /// Tinh DP trang thai
        G[mask][i] = G[mask][i-1] + (mask >> i & 1) * G[mask ^ (1 << i)][i-1];
    }
    
    /// Tinh ket qua
    F[mask] = G[mask];
}

Iterative DP SOS [2]

👤Author: @SPyofgame
🏷️Code Tag: DP SOS, DP Space Saving
💡Comment: Tối ưu bộ nhớ quy hoạch động.
⏳Time Complexity:

$O(2^n\times n)$
💾Space Complexity:

$O(2^n)$

/// Base case cua DP
for (int mask = 0; mask < (1 << n); ++mask) /// O(2^n)
    F[mask] = A[mask];

/// Duyet theo tung vi tri [i] truoc
for (int i = 0; i < n; ++i) /// O(n)
{
    /// Duyet qua cac mask
    for (int mask = 0; mask < (1 << n); ++mask) /// O(2^n)
    {
        /// Tinh DP trang thai
        F[mask] += (mask >> i & 1) * F[mask ^ (1 << i)];
    }
}

---

F. Ứng dụng

1) Dạng bài liên quan

2) Dạng bài thường gặp

3) Bài tập để luyện

• CF165E - Compatible Numbers
• CF383E - Vowels
• CF449D - Jzzhu and Numbers
• CF800D - Varying Kibbits

---

Z. Phản hồi từ người đọc

• Thả tim nếu bạn thấy bài viết hay và hữu ích nhé UwU.