# Chuyên Đề Quy Hoạch Động Trạng Thái - DP BITMASK
* [Kiến Thức Cần Biết](#Kiến-Thức-Cần-Biết)
* [Giới Thiệu](#Giới-Thiệu)
* [Các toán tử thao tác BIT ( Bitwise Operators ) cơ bản, các hàm thao tác BIT và các phép toán Bitmask thông dụng](#Các-toán-tử-thao-tác-BIT--Bitwise-Operators--cơ-bản-các-hàm-thao-tác-BIT-và-các-phép-toán-Bitmask-thông-dụng)
* [Phép toán Bitwise](#Phép-toán-Bitwise-)
* [Các hàm thao tác Bit thông dụng](#Các-hàm-thao-tác-Bit-thông-dụng)
* [Các phép toán Bitmask thông dụng](#Các-phép-toán-Bitmask-thông-dụng-)
* [Định Nghĩa Bitmask](#Định-Nghĩa-Bitmask)
* [Biểu diễn tập con bằng bitmask](#Biểu-diễn-tập-con-bằng-bitmask)
* [Nhắc lại về "Trạng thái quy hoạch động"](#Nhắc-lại-về-Trạng-thái-quy-hoạch-động)
* [Quy Hoạch Động Bitmask](#Quy-Hoạch-Động-Bitmask)
* [Dấu hiệu nhận biết Quy Hoạch Động Bitmask](#Dấu-hiệu-nhận-biết-Quy-Hoạch-Động-Bitmask)
* [Chú ý thêm](#Chú-ý-thêm)
* [Bài tập áp dụng](#Bài-tập-áp-dụng)
* [Tài liệu tham khảo](#Tài-liệu-tham-khảo)

## Kiến Thức Cần Biết
**Để đọc hiểu bài viết sau một cách hiệu quả, bạn đọc nên có sẵn các kiến thức về :**
* [Nhập môn Quy hoạch động](https://wiki.vnoi.info/translate/topcoder/dynamic-programming)
* [Quy Hoạch Động Cơ Bản (Phần 1)](https://wiki.vnoi.info/algo/dp/basic-dynamic-programming-1.md)
* [Quy Hoạch Động Cơ Bản (Phần 2)](https://wiki.vnoi.info/algo/dp/basic-dynamic-programming-2.md)
* [Các phép toán với BIT](https://wiki.vnoi.info/algo/basic/bitwise-operators.md).

## Giới Thiệu
**Quy hoạch động (DP)** là một kỹ thuật mạnh mẽ được sử dụng để giải các bài toán tối ưu bằng cách chia chúng thành các bài toán con đơn giản hơn. Bằng việc biểu diễn các bài toán con **thông qua các dãy bit** (gọi là các trạng thái) và sử dụng trạng thái nhỏ hơn để cập nhật kết quả cho các trạng thái lớn hơn, ta có một kĩ thuật rất hiệu quả để thay thế quay lui - nhánh cận, hoặc giải các bài toán quy hoạch động đếm cấu hình với số phần tử nhỏ. Khi kết hợp với **bitmask**, **DP** trở nên linh hoạt hơn, đặc biệt trong các bài toán liên quan đến tập hợp con, hoán vị hoặc các trạng thái có thể biểu diễn bằng số nhị phân.

**Quy Hoạch Động Bitmask** là 1 phương pháp để giải quyết tốt nhiều bài toán yêu cầu xử lí nhiều lớp về trạng thái và cũng là ứng dụng khá quan trọng trong nhiều bài toán có dữ liệu có thể đưa về xử lí bằng **BIT**.

**Quy Hoạch Động Bitmask** có thể dùng để giải 1 vài bài toán nhánh cận, cũng có thể nói rằng **Quy Hoạch Động Bitmask** là 1 cách vét thông minh và có độ chính xác cao.

Trong bài viết này, tôi sẽ giới thiệu tới các bạn kĩ thuật sử dụng **bitmask** kết hợp với các bài toán **quy hoạch động - Quy hoạch động bitmask**.

## Các toán tử thao tác BIT ( Bitwise Operators ) cơ bản, các hàm thao tác BIT và các phép toán Bitmask thông dụng

### Phép toán Bitwise :
Nếu trong các hệ thập phân có phép toán cộng, trừ, nhân, chia , … thì trong hệ nhị phân chúng ta có phép toán **AND, OR, NOT, XOR, dịch trái, dịch phải** và được biểu diễn cụ thể hơn ở dưới đây :
* **AND (&) : Trả về 1 nếu cả 2 Bit đều là 1.**
* **AND** trả về True ***khi và chỉ khi cả hai toán hạng*** là True.
* Ví dụ, ta có: **$0b11100010$ & $0b10101111 = 0b10100010$**
* **OR (|) : Trả về 1 nếu ít nhất 1 Bit là 1.**
* **OR** trả về True ***khi và chỉ khi ít nhất một toán hạng*** là True.
* Ví dụ, ta có: **$0b11100010 | 0b10101111 = 0b10101111$**
* **XOR (^) : Trả về 1 nếu các Bit khác nhau ngược lại thì trả về 0**.
* **XOR** trả về True ***khi và chỉ khi hai toán hạng có giá trị khác nhau***. Một cách hiểu khác cho **XOR** là phép cộng theo modulo 2.
* Ví dụ, ta có : **$0b11100010$ ^ $0b10101111 = 0b01001101$**
* **NOT (~) : Đảo ngược tất cả các Bit.**
* Toán tử Bitwise **NOT** có lẽ là toán tử đơn giản nhất. Toán tử này nhận vào một toán hạng A và trả về phần bù của toán hạng này. Nói cách khác, định nghĩa của **NOT** là ***trả về False khi và chỉ khi toán hạng là True và ngược lại***.
* Ví dụ, ta có : **$0b10100100 = 0b01011011$**
* **Chú ý** : biểu thức trên chỉ đúng trong trường hợp đầu vào là kiểu số có **8 bit**. Cụ thể hơn, cần chú ý: Khi sử dụng phép **NOT**, những bit không sử dụng ở bên trái cũng sẽ được bật lên. Chẳng hạn, khi thực hiện phép **$0b10$** với kiểu số char (**8 bit**), ta nhận được **$0b11111101$** thay vì **$0b01$**. Trong đa số trường hợp, ta sẽ cần phải tắt các bit được bật thừa này đi.
* **BITSHIFT LEFT (<<) : Dịch chuyển các Bit sang trái.**
* Định nghĩa của toán tử **Bitshift Left** là dịch tất cả các bit trong một số nguyên sang trái một lượng nào đó. Nói cách khác, trong phép toán **$a << b$**, các bit của a được dịch sang trái b lần.
* Ví dụ, xét số **$5 = 0b101$**, nếu thực hiện phép toán **$0b101<<2$**, ta nhận được **$0b10100 = 20$**.
* Nếu quan sát kỹ, bạn sẽ nhận thấy một tính chất thú vị sau của phép toán **Bitshift Left**: **$a << b = a * 2^b$** . Ta có tính chất này do phép toán **Bitshift Left** **$a << b$** có thể hiểu là **thêm b chữ số 0 vào cuối biểu diễn nhị phân của số a**. Điều này tương tự như việc thêm một chữ số 0 vào cuối biểu diễn thập phân của một số sẽ nhân số đó thêm 10 lần.
* **Chú ý** : Với C++, không nên để phép toán **$a << b$** của bạn bị tràn số (bit được left shift đến quá giới hạn của kiểu số đang sử dụng) vì sẽ có trường hợp code của bạn bị UB.
* **BITSHIFT RIGHT (>>) : Dịch chuyển các Bit sang phải.**
* Nếu như **Left Shift** là **thêm chữ số 0 vào bên phải của một số nguyên ở dạng nhị phân**, ta có thể hiểu **Right Shift** là **xóa các chữ số ở bên phải.**
* Ví dụ, xét số **$13 = 0b1101$**, ta có **$0b1101 >> 2 = 0b11$**.
* Tương tự với **Bitshift Left**, ta cũng có tính chất **$$a >> b = \left\lfloor\frac{a}{2^b} \right\rfloor
$$** với nguyên không âm.

| a | b | AND | OR | XOR |
|:---:|:---:|:---:| --- |:---:|
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |

### Các hàm thao tác Bit thông dụng
**Compiler GCC** (là Compiler đi kèm với Codeforces, Dev-C++, và được sử dụng trên các OJ phổ biến) hiện nay hỗ trợ một số các hàm liên quan tới xử lý bit giúp ta thực hiện một số các phép tính thông dụng với độ phức tạp thời gian.

Bảng các hàm thao tác Bit :

| Tên thao tác | Tên hàm | Giá trị trả về | Trường hợp UB |
|------------------------|------------------------|------------------------------|-------------------|
| Population Count | `__builtin_popcountll(x)` | Số Bit bật | |
| Parity | `__builtin_parityll(x)` | Số Bit bật modulo 2 | |
| Log2 | `std::__lg(x)` | $log_2(x)$| |
| Count Trailing Zeroes | `__builtin_ctzll(x)` | Số Bit 0 ở cuối | `x == 0` |
| Count Leading Zeroes | `__builtin_clzll(x)` | Số Bit 0 ở đầu | `x == 0` |
| Find First Set | `__builtin_ffsll(x)` | Số thứ tự của Bit 1 đầu tiên | |
### Các phép toán Bitmask thông dụng :
* Kiểm tra xem bit thứ i có được thiết lập không: **mask & (1 << i)**
* Thiết lập bit thứ i: **mask | (1 << i)**
* Hủy thiết lập bit thứ i: **mask & ~(1 << i)**
* Chuyển đổi trạng thái của bit thứ i: **mask ^ (1 << i)**

## Định Nghĩa Bitmask
Bitmask hay còn được gọi là bộ Boolean nhỏ, nhẹ (hỗ trợ riêng cho C/ C++/ Java) là một dãy bit thể hiện nhiều trạng thái của một đối tượng.

Như chúng ta đã biết, một số nguyên trong máy tính được biểu diễn bằng một chuỗi hoặc nhiều chuối bit với nhau. Do đó, chúng ta có thể sử dụng các số nguyên để biểu diễn cho bitmask. Sau đó, tất cả các trạng thái trong một bitmask chỉ liên quan đến các phép thao tác bit. Điều này làm cho nó trở thành một lựa chọn hiệu quả hơn so với các cấu trúc dữ liệu: vector, set, bitset, … trong C++. Tốc độ của bitmask có thể nhanh hơn so với các CTDL trên làm cho nó trở nên rất quan trọng trong lập trình cạnh tranh.

Chúng ta đã biết rằng một số nguyên được biểu diễn bởi chuỗi bit. Bit thứ 1 sẽ cho ta biết trạng thái của phần tử thứ 1 có được chọn hay không, tương tự với các phần tử thứ 2, thứ 3, v.v. Ví dụ, xét một tập hợp A = {1, 2, 3, 4, 5} có 5 phần tử và chúng ta chọn ra tập con B = {1, 3, 4}. Bitmask biểu diễn điều này dưới dạng dãy nhị phân là 01101 hoặc 13 ở dạng thập phân).

Lưu ý: Trong chuyên đề này, các dãy bit được tính từ bên phải (vị trí nhỏ nhất) rồi tiến dần sang trái. Ví dụ là 0001 thì sẽ là 1 ở dạng thập phân.
## Biểu diễn tập con bằng bitmask

Ta có thể biểu diễn một tập con của một tập hợp bằng một xâu nhị phân, trong đó bit thứ $i$ bằng 0/1 khi phần tử thứ $i$ không/có nằm trong tập hợp. Xâu nhị phân này được gọi là **Bitmask**.

Giả sử có một tập hợp $S = {a_0, a_1, a_2, \dots, a_{n-1}}$. Xét một tập con $T = \{a_{i_1}, a_{i_2}, \dots, a_{i_k}\}$ của $S$. Khi đó ta có thể biểu diễn $T$ bằng một xâu nhị phân độ dài $n$, với bit thứ $i$ (ở đây là bit có giá trị cao thứ $i$ hay bit thứ$i$ từ phải sang) bằng 1 nếu $a_i$ nằm trong tập $T$:

$$
\text{mask}_T = 000 \dots 010 \dots 010 \dots 000
$$

với các vị trí bằng 1 là $i_1, i_2, \dots, i_k$.

---

Do ${mask}_T$ là một xâu nhị phân, ta có thể biểu diễn nó bằng một số ở dạng thập phân. Ví dụ:

- $12 = (1100)_2$ biểu diễn tập con $T = \{a_2, a_3\}$ của $S = \{a_0, a_1, a_2, a_3\}$
- $17 = (010001)_2$ biểu diễn tập con $T = \{a_0, a_4\}$ của $S = \{a_0, a_1, a_2, a_3, a_4, a_5\}$
- $0 = (000)_2$ biểu diễn tập con $T = \{\}$ của $S = \{a_0, a_1, a_2\}$

---

Khi duyệt tất cả các số từ $0$ đến $2^n - 1$, ta sẽ duyệt qua mọi xâu nhị phân độ dài $n$, và cũng là duyệt qua tất cả các tập con của $S = \{a_0, a_1, \dots, a_n\}$. Công việc duyệt này có độ phức tạp thời gian là $O(2^n)$.

## Nhắc lại về "Trạng thái quy hoạch động"

**Trạng thái (state)** là một khái niệm cơ sở của quy hoạch động. Khi giải quyết một bài toán quy hoạch động, chúng ta cần đi tìm mục tiêu của bài toán lớn, sau đó xác định ra những bài toán con (hay những trường hợp nhỏ hơn) của bài toán lớn - đó gọi là các **trạng thái**.

---

**Xét một ví dụ đơn giản:**

> Cho n đồng xu và giá tiền của mỗi đồng $(v_0, v_1, v_2, \dots, v_{n-1})$, cùng với một số nguyên $s$. Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng $s$ (biết rằng số lượng đồng xu không giới hạn).

---

Trong bài toán trên, mục tiêu là đi tìm số đồng xu nhỏ nhất sao cho tổng giá trị của chúng bằng $s$. Vậy các trạng thái sẽ là số lượng đồng xu nhỏ nhất để tổng bằng với $i$, mà $0 \leq i \leq s$. Muốn tìm ra trạng thái $i$, ta phải tìm ra các trạng thái $j < i$. Và một khi đã tìm được trạng thái $i$, ta có thể dễ dàng tìm ra trạng thái của $i + 1$.

---

Để lưu trữ các trạng thái, ta sẽ sử dụng mảng để lưu kết quả tính toán được mỗi bước (gọi là bảng phương án). Trong bài toán Quy hoạch động bitmask, một hoặc một số trạng thái sẽ có thể biểu diễn dưới dạng bitmask (thường là các dãy con, tập con), và như đã nói, bitmask cũng có thể được duyệt bằng các số nguyên. Thông qua các thao tác xử lý bit, ta có thể tra ra các trạng thái con của một trạng thái lớn (ví dụ như dãy nhị phân $000010$ là trạng thái trước của $100010$, tương ứng với hai số nguyên là $2$ và $34$).

## Quy Hoạch Động Bitmask
* Kĩ thuật dùng **Bitmask** là một trong những kĩ thuật quan trọng mà chúng ta cần phải biết.
* Chúng thường được nhận dạng khi với các thông số cho trước trong đề ta có thể giải quyết bài toán bằng độ phức tạp cấp số nhân.
* Trong kĩ thuật này, ta cần lưu ý rằng các bài toán con sẽ được lưu trong một mảng được gọi là mảng trạng thái. Trạng thái hiện tại sẽ cập nhật dữ liệu của trạng thái trước. Ví dụ: $000010$ là trạng thái trước của $100010$.
* Kĩ thuật này có thể giải thay thế một số bài toán quay lui, nhánh cận và giải nhiều bài toán đếm với cấu hình nhỏ.
* Có **2 loại chính**:
* **Loại thứ 1** : Là loại mà cấu hỉnh vị trí của giá trị không thay đổi - tức là cách chọn cố định.
* **Loại thứ 2** : Là loại mà phụ thuộc vào cách sắp xếp thứ tự giá trị để bài toán tối ưu.
* Thông thường, bảng sẽ được xây dựng như sau:
* F[X]: chỉ lưu giá trị tại trạng thái X, chủ yếu dùng cho loại 1.
* F[X, I]: lưu giá trị tại thạng thái X là I được thêm vào cuối cùng.

---
**Xét ví dụ đơn giản sau**
>Cho hai số nguyên dương $N$ và số tự nhiên $K$ $(N \leq 15, K \leq N)$. Một hoán vị của dãy $[a_1, a_2, \dots, a_n]$ là một cách sắp xếp lại dãy $a$ sao cho mọi phần tử của dãy đều xuất hiện chính xác một lần. Để hoán vị dãy có độ dài $N$, dãy $[1, 2, \dots, N]$ mà trong hoán vị đó, hai phần tử liền tiếp chênh lệch nhau không quá $K$.
Ví dụ, với $N = 4$, $K = 2$, $[1, 2, 3, 4]$ là một hoán vị thoả mãn, còn $[4, 1, 3, 2]$ là một hoán vị không thoả mãn do $4 - 1 = 3 > 2$.

---

**Phân tích**

Cách làm tự nhiên nhất đối với bài toán trên là sinh ra mọi hoán vị có thể của dãy $[1, 2, \dots, N]$ (tạm gọi là dãy $a$) bằng cách sử dụng thuật toán quay lui. Độ phức tạp thời gian là $O(N!)$, với $N \leq 15$ là không thể sử dụng cách này.

Ta có thể áp dụng tư tưởng quy hoạch động, với mỗi trạng thái phân tử vị trí $i$ phải xác định $a_i - 1$ của một khoảng không quá $K$. Cách này sẽ tạo ra tối đa các cặp $dp[i][p]$ là số lượng dãy hoán vị sao cho phần tử thứ $i$ là $p$, dẫn đến $dp[i - 1][p]$. Tuy nhiên, cách gọi này không đảm bảo được tính chính xác của hoán vị và cần các phần tử dãy ban đầu phải xuất hiện chính xác một lần.

Để có được tính chất này, thay vì chỉ dùng vị trí, ta dùng hẳn một tập hợp để lưu lại tất cả các vị trí đã được thêm vào dãy trước đó. Gọi $dp[X][p]$ là số lượng dãy là hoán vị của $X \cup p$ và có phần tử cuối cùng được thêm vào $X$ là $p$. Khi thêm một phần tử $q$ vào $X$, ta cần chắc chắn rằng $q \notin X$, và $|q - p| \leq K$. Như vậy:

$$
\forall q \notin X, dp[X \cup \{q\}][q] = \sum_{p: |q - p| \leq K} dp[X][p].
$$

Với trường hợp cơ sở, ta có thể chọn $dp[\emptyset][\infty] = 0$. Dĩ nhiên, ta không thể biểu diễn $\infty$ trong mảng khi cài đặt được; trong trường hợp này ta có thể thay thế nó bằng 0 và chấp nhận mọi trường hợp với $q$ vào $X$ nếu xuất hiện $p = 0$. Kết quả của bài toán là tổng số dãy được tạo ra từ dãy ban đầu với đầy đủ phần tử từ 0 môi trường $X$ cuối cùng, tức:

$$
\sum_{p=1}^{N} dp[a][p].
$$

Còn để biểu diễn tập hợp $X$ khi cài đặt, ta sử dụng bitmask như đã nói ở trên.

- Một tập hợp $X$ của $a$ đều có thể biểu diễn bằng một dãy nhị phân độ dài $N$, dương một số nguyên dương. Chẳng hạn, với $N = 4$, dãy $[0, 1, 0, 1]$ được biểu diễn thành $dp[5][1]$ (tức là $(0101)_2 = 5$. Gọi biểu diễn nhị phân này là `mask`.

- **Biểu diễn nhị phân của $X$ khi $X = a$ là mask = (1 << N) - 1.**

- **Biểu diễn của $q \in X$ là ((mask >> q) & 1) == 1.**

- **Biểu diễn của $X \cup \{q\} = mask | (1 << q).$**

Để duyệt qua mọi trạng thái tập $X$, ta duyệt mọi số nguyên tương ứng từ $0$ đến $2^N - 1$ cho giá trị của `mask`.

Trong bài toán này, hoán vị phải được tạo thành bởi các số từ 1 đến $N$. Nếu sử dụng cách biểu diễn trên, bit ở vị trí thứ 0 không biểu diễn cái gì cả, hơn nữa phải dùng $N + 1$ bit mới biểu diễn hết được $N$ số này. Vì vậy, thay vì dùng bit thứ $q$ để biểu diễn việc $q$ có thuộc $X$ hay không, ta dùng bit thứ $q - 1$. Bằng cách này, ta chỉ cần đúng $N$ bit để biểu diễn tập hợp mà không lãng phí bit nào.

---
**Cài đặt**

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = (1 << 15) + 1;

int n, k;
long long dp[MAXN][16];

// Lấy bit thứ k của số x
int getBit(int x, int k) {
    return (x >> k) & 1;
}

// Hàm giải bài toán
int solve(int n, int k) {
    // Khởi tạo dp
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int j = 0; j <= n; j++) {
            dp[mask][j] = 0;
        }
    }

    // Trường hợp cơ sở
    dp[0][0] = 1;

    // Duyệt qua tất cả các trạng thái
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int q = 1; q <= n; q++) {
            // Kiểm tra xem q đã nằm trong tập hợp chưa
            if (getBit(mask, q - 1)) continue;

            for (int p = 0; p <= n; p++) {
                // Kiểm tra chênh lệch giữa q và p
                if (p != 0 && abs(q - p) > k) continue;

                // Thêm q vào tập hợp
                int newMask = mask | (1 << (q - 1));

                dp[newMask][q] += dp[mask][p];
            }
        }
    }

    // Tính kết quả
    long long res = 0;
    int fullMask = (1 << n) - 1;
    for (int j = 1; j <= n; j++) {
        res += dp[fullMask][j];
    }
    return res;
}

// Hàm chính
int main() {
    cout << "Nhập n và k: ";
    cin >> n >> k;

    if (n > 15 || k > n) {
        cout << "Giá trị n và k không hợp lệ (n <= 15, k <= n)." << endl;
        return 0;
    }

    int result = solve(n, k);
    cout << "Số lượng hoán vị thỏa mãn là: " << result << endl;

    return 0;
}

Độ phức tạp về thời gian của cách cài đặt trên là $\mathcal{O}(N^2 \times 2^N)$, còn độ phức tạp về không gian là $\mathcal{O}(N \times 2^N)$.

## Dấu hiệu nhận biết Quy Hoạch Động Bitmask

Dấu hiệu đầu tiên để nhận biết những bài toán có khả năng sử dụng quy hoạch động bitmask, đó là ràng buộc dữ liệu. Thông thường, những bài toán này có độ dài của dãy số, của xâu kí tự, của tập hợp,... đều không vượt quá 20 (có thể là những con số như 10, 15, 16, ...). Lý do là vì với ràng buộc 20, thì số lượng tập con của tập hợp sinh ra sẽ là $2^{20} \approx 10^6$; đây là ràng buộc phù hợp để sử dụng các số nguyên duyệt trạng thái, rồi kết hợp với các kĩ thuật tính toán khác mà không bị **Time Limit Exceeded**.

Do việc sử dụng các bitmask để biểu diễn bài toán con, nên những bài toán quy hoạch động bitmask thường liên quan tới việc lựa chọn dãy con, tập con. Bảng phương án trong dạng bài này sẽ lưu trữ kết quả của các trạng thái (biểu diễn thông qua những số nguyên), chẳng hạn như $dp[10]$ thì ta có thể ngầm hiểu là $dp[1010_2] = 10$.

## Chú ý thêm

Ta thấy rằng nếu $m$ lớn, thuật toán cũng sẽ mất rất nhiều thời gian để chạy. Vì vậy, để thực hiện được phương pháp này thì $m$ cần phải đủ nhỏ, thường là $m \leq 20$ nếu thuật toán chỉ yêu cầu ta phải duyệt qua các tập hợp.

Việc sử dụng biểu diễn bitmask của tập hợp và QHĐ bitmask giúp chúng ta kiểm tra được mọi tập hợp con của một tập hợp lớn hơn. Do vậy, trong nhiều trường hợp, đây là phương pháp đơn giản và đáng để thử khi muốn kiểm điểm một cách hiệu quả từ các subtask bé, cũng như có một code chắc chắn để làm tiếp với các subtask lớn hơn.

## Bài tập áp dụng

## Tài liệu tham khảo
[Quy Hoạch Động Bitmask - VIBLO](https://viblo.asia/p/quy-hoach-dong-bitmask-Yym40r85L91)
[Quy Hoạch Động Bitmask - VNOI WIKI](https://wiki.vnoi.info/algo/dp/dp-bitmask)
[Phép toán bit - VNOI WIKI](https://wiki.vnoi.info/algo/basic/bitwise-operators.md)