---
title: Kings Problem
author: minhnguyent546
date: 8/13/2023
---

###### Tags: dp, state-compression, bitmask-dp

# Áp dụng kỹ thuật quy hoạch động nén trạng thái để giải bài toán Quân vua

## Giới thiệu

State compression DP hay DP nén trạng thái là một kỹ thuật nén các state dưới dạng một số nguyên.

Những bài toán áp dụng kỹ thuật này thường có những đặc điểm:
- Bài toán trên mảng $2D$
- Có một chiều có giá trị không quá lớn
- Trạng thái mỗi ô chỉ phụ thuộc vào những ô kề (chung cạnh hoặc chung góc)

Đặc điểm cuối cùng là đặc điểm quan trọng để có thể áp dụng kỹ thuật này. Vì mỗi ô chỉ phụ thuộc trạng thái những ô kề nên ta sẽ duyệt ma trận theo cột $\rightarrow$ cột, hàng $\rightarrow$ hàng và lưu trạng thái của một số ô trước đó hoặc cột trước đó để kiểm tra.

Để dễ hình dung hơn chúng ta hãy cùng đi vào bài toán dưới đây.

## Ví dụ bài toán [Counting Tilings](https://cses.fi/problemset/task/2181/)

**Tóm tắt đề bài:** cho một ma trận kích thước $n \times m$. Đếm số cách phủ đầy ma trận này sử dụng những viên gạch $2 \times 1$ và $1 \times 2$.

**Giới hạn:**
- $1 \leq n \leq 10$
- $1 \leq m \leq 1000$

**Lời giải:**
- Chúng ta sẽ lần lượt xử lý từng ô theo thứ tự cột $\rightarrow$ cột, hàng $\rightarrow$ hàng. Đặt $dp[i][j][mask]$ là số cách phủ sao cho:
- Các ô từ $(0, 0) \rightarrow (i, j - 1)$ đã được phủ
- Các ô từ $(i + 1, j) \rightarrow (n - 1, m - 1)$ còn trống
- $mask$ biểu diễn trạng thái của $n$ ô còn lại. Ô ở hàng $k$ còn trống nếu bit thứ $k$ bằng $0$ và ngược lại.
- Hình minh họa với $n = 5, m = 4$ cho $dp[1][2][01001_2]$ (ô $(1, 2)$ là ô đang xét, $n$ ô trạng thái được tô viền đậm, các ô hồng ứng với vị trí chứa bit $1$):
<p style="text-align: center;"><img src="https://hackmd.io/_uploads/BJl86_dh2.png" style="height: 210px;"></p>

- Khi xét đến $dp[i][j][mask]$ có hai trường hợp:
- Bit thứ $i$ của $mask$ bằng $0$, tức ô $(i, j)$ sẽ là ô trống, khi đó ô $(i, j - 1)$ phải được phủ. Số cách phủ là $dp[i - 1][j][mask \oplus 2^i]$. Hình minh họa:
<p style="text-align: center;"><img src="https://hackmd.io/_uploads/BkryeYdhn.png" style="height: 210px;"></p>

- Bit thứ $i$ của $mask$ bằng $1$, tức ô $(i, j)$ bị phủ
- Nếu dùng viên gạch $2 \times 1 (i > 0)$:
- Ở trạng thái hiện tại: ô $(i, j)$ và ô $(i - 1, j)$ phải được phủ
- Ở trạng thái trước đó: ô $(i, j - 1)$ phải được phủ và ô $(i - 1, j)$ phải trống
- Do đó số cách phủ là $dp[i - 1][j][mask \oplus 2^{i - 1}]$
<p style="text-align: center;"><img src="https://hackmd.io/_uploads/HJzQetd33.png" style="height: 210px;"></p>

- Nếu dùng viên gạch $1 \times 2$: ô $(i, j - 1)$ ở trạng thái trước đó phải trống. Số cách phủ là $dp[i - 1][j][mask \oplus 2^i]$
<p style="text-align: center;"><img src="https://hackmd.io/_uploads/B1uBxFd3n.png" style="height: 210px;"></p>

- Đáp án chính là $dp[n - 1][m - 1][2^n - 1]$.

**Độ phức tạp:** $\mathcal{O}(m \times n \times 2^n)$.

Cài đặt mẫu có thể tham khảo [tại đây](https://ideone.com/C2u4PV).

## Áp dụng giải bài [Quân vua](https://dmoj.ctu.edu.vn/problem/cictcpc2023_king)

**Lời giải:**
- Đặt giá trị ô $(i, j) = 1$ nếu ô $(i, j)$ có quân vua. Ngược lại giá trị ô $(i, j) = 0$. Dễ thấy bài toán trở thành tìm số cách đặt $k$ số $1$ vào ma trận $n \times n$ sao cho không có hai ô nào chung góc đều mang giá trị $1$.
- Đặt $dp[i][j][cnt][mask]$ là số cách đặt khi xét đến ô $(i, j)$, tổng số quân vua đã đặt được là $cnt$, trạng thái của $n$ ô trước đó tính từ ô $(i, j)$ là $mask$. Chú ý $mask$ không thể chứa hai bit 1 cạnh nhau.
- Khi xét đến $dp[i][j][cnt][mask]$ có hai trường hợp:
- Bit thứ $i$ của $mask$ là $0$ hay ô $(i, j)$ mang giá trị $0$: ô $(i, j - 1)$ có thể có giá trị $0$ hoặc $1$:
$$
dp[i][j][cnt][mask] = \begin{cases}
dp[i - 1][j][cnt][mask, mask \oplus 2^i]& \text{nếu $i > 0$} \\
dp[n - 1][j - 1][cnt][mask, mask \oplus 2^i]& \text{nếu $i = 0$}
\end{cases}
$$
- Bit thứ $i$ của $mask$ là $1$ hay ô $(i, j)$ mang giá trị $1$: khi đó các ô $(i - 1, j - 1), (i, j - 1), (i + 1, j - 1)$ phải có giá trị $0$:
$$
dp[i][j][cnt][mask] = \begin{cases}
dp[i - 2][j][cnt - 1][mask \oplus 2^i] & \text{nếu $i \geq 2$} \\
dp[n - 1][j - 1][cnt - 1][mask \oplus 2^i] & \text{nếu $i < 2$}
\end{cases}
$$
- Đáp án chính là $\sum\limits_{mask} dp[n - 1][n - 1][k][mask]$.

**Độ phức tạp**: $\mathcal{O}(n^2 \times k \times 2^n) = \mathcal{O}(n^4 \times 2^n)$.

**Một cách tiếp cận khác tối ưu hơn:**
- Thay vì xét qua từng ô thì ta sẽ đi qua từng cột và xét mọi trạng thái có thể của cột đang xét.
- Đặt $dp[i][mask][cnt]$ là số cách đặt khi xét đến cột $i$, trạng thái của cột đang xét là $mask$, tổng số quân vua đã đặt là $cnt$. Khi đó:
$$dp[i][mask][cnt] = \sum\limits_{prev\_mask} dp[i - 1][prev\_mask][cnt - count(mask)]$$
- $prev\_mask$ thỏa mãn những điều kiện:
- Không tồn tại vị trí $k$ mà $mask_k$ và $prev\_mask_k$ đều bằng $1$.
- Không tồn tại vị trí $k$ mà $mask_k$ và $prev\_mask_{k - 1}$ đều bằng $1$.
- Không tồn tại vị trí $k$ mà $mask_k$ và $prev\_mask_{k + 1}$ đều bằng $1$.
- $count(mask)$ là số bit $1$ trong $mask$
- Ta có thể sinh trước các state ($mask$) thỏa mãn không chứa hai bit $1$ kề nhau để giảm độ phức tạp khi duyệt.

**Độ phức tạp:** Số dãy nhị phân độ dài $n$ không chứa hai bit $1$ kề nhau là $F_{n + 2}$ với $F_i$ là số fibonacci thứ $i$. Do đó độ phức tạp trong trường hợp xấu nhất là $\mathcal{O}(n \times k \times F_{n + 2}^2) = \mathcal{O}(n^3 \times F_{n + 2}^2)$. Thực tế cách cài đặt này có thể chạy đến $n = 16$ (bạn có thể thử sức với [bài D ICPC miền Bắc 2023](https://oj.vnoi.info/problem/icpc23_mb_d)).

## Tham khảo

- https://usaco.guide/adv/dp-more
- https://en.oi-wiki.org/dp/state/