DP broken profile

DP broken profile (quy hoạch động theo "đường biên gãy") là kỹ thuật DP điền một lưới $n\times m$ theo từng ô một, chỉ nhớ trạng thái của các ô (hoặc các cạnh) nằm trên đường biên giữa phần đã xử lý và phần chưa xử lý. Với bài lát domino, số trạng thái là $2^m$ và độ phức tạp là $O(n·m·2^m)$, thay vì liệt kê $2^{nm}$ cấu hình. Khi ràng buộc là liên thông (đếm chu trình Hamilton, nối ống thành một vòng kín), ta dùng biến thể plug DP: mỗi vị trí trên biên nhớ thêm "đoạn đường này nối với vị trí nào", và chỉ lưu các trạng thái thực sự gặp trong một bảng băm.

Trang này giả định bạn đã quen DP bitmask (mask là tập con). Ở đây mask không còn là "tập đã chọn" mà là "hình dạng của biên".

Ý tưởng / Trực giác

Đường biên gãy

Hãy hình dung ta lấp lưới theo thứ tự đọc sách: hàng 0 từ trái sang phải, rồi hàng 1, ... Khi đang đứng ở ô $(i,j)$, "biên giới" giữa vùng đã quyết định và vùng chưa quyết định không phải một đường thẳng mà là một đường gấp khúc (broken profile):

       cột:  0   1   2   3   4
hàng i-1:   [x] [x] [x] [x] [x]      x = đã quyết định
                    ___________      biên cao: dưới hàng i-1 (cột 2..4)
hàng i  :   [x] [x]|[@] [ ] [ ]      @ = ô đang xét (i, j=2)
            _______|                 biên thấp: dưới hàng i (cột 0..1)
hàng i+1:   [ ] [ ] [ ] [ ] [ ]

Đi từ trái sang phải, biên nằm dưới hàng i ở cột 0..1 rồi bước LÊN,
nằm dưới hàng i-1 ở cột 2..4.

Câu hỏi mấu chốt: để điền tiếp phần còn lại, ta cần nhớ gì về quá khứ? Chỉ cần biết, trong $m$ ô sát ngay dưới đường biên, ô nào đã bị một viên gạch đặt trước đó "thò" vào chiếm chỗ. Mọi chi tiết khác (gạch ở các hàng trên đặt thế nào) không ảnh hưởng tới cách lấp phần còn lại. Hai cách điền quá khứ khác nhau nhưng để lại cùng một biên thì có cùng số cách hoàn thành, nên ta gộp chúng vào một trạng thái. Đó là lý do DP đúng.

Mã hoá biên bằng bitmask $m$ bit, bit $k$ ứng với ô của biên ở cột $k$:

• Khi đứng ở ô $(i,j)$: bit $j$ là chính ô $(i,j)$; các bit $k>j$ là ô $(i,k)$ của hàng hiện tại; các bit $k<j$ là ô $(i+1,k)$ của hàng dưới (đã bị gạch dọc chiếm trước).
• bit $=1$: ô đó đã bị chiếm; bit $=0$: còn trống.

Xử lý ô $(i,j)$: nếu bit $j=1$ thì ô đã bị phủ, chỉ việc tắt bit và đi tiếp. Nếu bit $j=0$ thì bắt buộc phủ nó ngay bây giờ (sau bước này không còn cơ hội nào nữa), thử mọi viên gạch có ô $(i,j)$ là ô đầu tiên theo thứ tự duyệt. Mỗi lựa chọn cho một mask mới.

Vì sao theo từng ô chứ không theo từng cột?

DP bitmask theo cột chuyển cả một cột một lúc, phải duyệt mọi cặp (mask cũ, mask mới) tương thích: tới $O(4^m)$ cặp mỗi cột, hoặc phải sinh bằng quay lui. Broken profile chuyển một ô mỗi bước, mỗi trạng thái có tối đa 2 đến 3 lựa chọn (có thể là 0, khi đó nhánh chết), nên tổng là $O(nm·2^m)$ và code gần như không đổi khi thêm loại gạch mới.

Khi ràng buộc là liên thông: plug DP

Với bài "đếm số chu trình Hamilton trên lưới" (một vòng kín đi qua mọi ô trống đúng một lần), mỗi ô trống có đúng 2 cạnh của vòng đi qua. Biên lúc này cắt qua các cạnh giữa hai ô; mỗi cạnh bị cắt gọi là một plug (phích cắm): có hoặc không có đoạn đường đi qua nó.

Chỉ biết "plug nào có đường" là chưa đủ. Phần đã xử lý là một tập các đoạn đường rời nhau, mỗi đoạn có hai đầu thò qua biên. Nếu sau này ta nối hai đầu của cùng một đoạn thì sẽ khép một chu trình con, trong khi còn những ô chưa đi, và cấu hình bị hỏng. Vậy trạng thái phải nhớ thêm: hai plug nào thuộc cùng một đoạn.

Lưới là đồ thị phẳng và các đoạn đường không cắt nhau, nên nhìn dọc theo biên từ trái sang phải, các cặp đầu mút lồng nhau đúng như một dãy ngoặc hợp lệ: đầu trái của một đoạn là (, đầu phải là ). Hai đoạn không thể "đan chéo" kiểu ( [ ) ] vì như thế chúng phải cắt nhau ở phía trên biên. Mỗi plug chỉ cần 3 giá trị: không có, (, ), tức là 2 bit, và đầu kia của một plug tìm được bằng cách đếm ngoặc.

Ví dụ chạy tay

Lát domino lưới $2\times 2$

Đếm số cách lát kín lưới $2\times 2$ bằng domino (đáp số đúng là 2: hai thanh ngang hoặc hai thanh dọc). Thứ tự duyệt: $(0,0),(0,1),(1,0),(1,1)$. Viết mask dưới dạng [b0 b1] (bit 0 trước). Khởi tạo dp[00] = 1.

Ô (0,0), mask [0 0]: ô trống, phải phủ
  - gạch dọc  (0,0)+(1,0): bật b0 (ô (1,0) bị chiếm)  -> [1 0]
  - gạch ngang (0,0)+(0,1): bật b1 (ô (0,1) bị chiếm) -> [0 1]

Ô (0,1):
  - từ [1 0]: b1 = 0, ô trống. Ngang: hết lưới. Dọc (0,1)+(1,1): bật b1 -> [1 1]
  - từ [0 1]: b1 = 1, đã bị phủ: tắt b1 -> [0 0]

Ô (1,0):
  - từ [1 1]: b0 = 1, đã bị phủ: tắt b0 -> [0 1]
  - từ [0 0]: b0 = 0. Dọc: hết lưới. Ngang (1,0)+(1,1): bật b1 -> [0 1]

Ô (1,1):
  - từ [0 1] (giá trị 2): b1 = 1, tắt -> [0 0]

Bảng giá trị dp sau mỗi ô (ô trống là 0):

Đáp án dp[00] = 2. Ở ô $(1,0)$ ta thấy hai nhánh (hai thanh dọc, hai thanh ngang) cùng rơi vào trạng thái [0 1] và được gộp lại: đây chính là chỗ DP tiết kiệm so với duyệt.

Plug DP: chu trình Hamilton trên lưới $2\times 3$

Lưới $2\times 3$ toàn ô trống có đúng 1 chu trình Hamilton (đi vòng theo chu vi). Với $m=3$ có $m+1=4$ plug, đánh số $p_0..p_3$. Khi xét ô $(i,j)$:

            p_{j+1} = U (cạnh đi từ trên xuống ô)
                |
   p_j = L -> [i,j] -> (sau khi xét: p_{j+1} = cạnh sang phải)
                |
            (sau khi xét: p_j = cạnh đi xuống)

Trạng thái viết là 4 ký tự $p_0{p}_1{p}_2{p}_3$, dấu . là không có plug.

Bắt đầu hàng 0:  . . . .

(0,0): L='.', U='.'  -> mở đoạn mới: xuống '(' , sang phải ')'
       ( ) . .

(0,1): L=')', U='.'  -> một plug, kéo tiếp xuống hoặc sang phải
       xuống:     ( ) . .
       sang phải: ( . ) .

(0,2): từ ( ) . .  : L='.', U='.', cần mở đoạn mới nhưng không có ô bên phải -> chết
       từ ( . ) .  : L=')', U='.', chỉ đi xuống được
       ( . ) .

Hết hàng 0: p3 phải trống (không có cạnh thò ra khỏi lưới), dịch mọi plug sang phải 1 vị trí:
       . ( . )

(1,0): L='.', U='(' -> không có hàng dưới, chỉ sang phải
       . ( . )
(1,1): L='(', U='.' -> sang phải
       . . ( )
(1,2): L='(', U=')' -> nối hai đầu của cùng một đoạn = khép chu trình.
       Đây là ô trống cuối cùng và không còn plug nào khác -> đếm được 1.

Hình vẽ chu trình tìm được:

 (0,0)---(0,1)---(0,2)
   |               |
 (1,0)---(1,1)---(1,2)

Trạng thái ( ) . . ở ô $(0,2)$ chết vì đoạn đang dở ở cột 1 và ô $(0,2)$ còn trống không thể có 2 cạnh (không có ô phải, cạnh trái và cạnh trên đều không có). Plug DP cắt được nhánh này ngay tại chỗ.

Cài đặt

Lát domino (C++)

Đếm số cách lát kín lưới $n\times m$ bằng domino $1\times 2$ và $2\times 1$, modulo ${10}^9+7$ (đúng dạng bài cnttiling):

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    if (m > n) swap(n, m); // keep m as the smaller side so 2^m stays small

    // dp[mask]: number of ways; bit k = 1 means the profile cell in column k
    // is already covered by an earlier tile.
    vector<long long> dp(1 << m, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vector<long long> ndp(1 << m, 0);
            for (int mask = 0; mask < (1 << m); mask++) {
                if (!dp[mask]) continue;
                long long ways = dp[mask];
                if (mask >> j & 1) {
                    // (i,j) already covered from above: clear bit j and move on
                    int nm = mask ^ (1 << j);
                    ndp[nm] = (ndp[nm] + ways) % MOD;
                    continue;
                }
                // (i,j) is empty and must be covered now
                if (i + 1 < n) { // vertical tile: (i,j) + (i+1,j)
                    int nm = mask | (1 << j);
                    ndp[nm] = (ndp[nm] + ways) % MOD;
                }
                if (j + 1 < m && !(mask >> (j + 1) & 1)) { // horizontal: (i,j) + (i,j+1)
                    int nm = mask | (1 << (j + 1));
                    ndp[nm] = (ndp[nm] + ways) % MOD;
                }
            }
            dp = move(ndp);
        }
    }
    cout << dp[0] << "\n"; // no tile sticks out of the grid
}

Kết quả kiểm tra: $2\times 3\to 3$, $3\times 4\to 11$, $4\times 4\to 36$, $8\times 8\to 12988816$.

Lát domino (Python)

import sys

MOD = 10**9 + 7

def count_tilings(n, m):
    if m > n:
        n, m = m, n                      # keep m as the smaller side
    dp = [0] * (1 << m)
    dp[0] = 1
    for i in range(n):
        for j in range(m):
            ndp = [0] * (1 << m)
            for mask, ways in enumerate(dp):
                if ways == 0:
                    continue
                if mask >> j & 1:        # covered from above
                    ndp[mask ^ (1 << j)] = (ndp[mask ^ (1 << j)] + ways) % MOD
                    continue
                if i + 1 < n:            # vertical tile
                    nm = mask | (1 << j)
                    ndp[nm] = (ndp[nm] + ways) % MOD
                if j + 1 < m and not (mask >> (j + 1) & 1):  # horizontal tile
                    nm = mask | (1 << (j + 1))
                    ndp[nm] = (ndp[nm] + ways) % MOD
            dp = ndp
    return dp[0]

n, m = map(int, sys.stdin.read().split())
print(count_tilings(n, m))

Mở rộng: gạch khác và ô cấm

Thêm loại gạch chỉ cần thêm nhánh trong khối "ô trống", với điều kiện mọi ô của viên gạch đều nằm trên biên 1 bit/cột. Sau khi xét ô $(i,j)$, bit $k\le j$ ứng với ô $(i+1,k)$ còn bit $k>j$ vẫn ứng với ô $(i,k)$ của hàng hiện tại. Vậy một viên gạch đặt tại $(i,j)$ chỉ được chiếm thêm các ô $(i,k)$ với $k>j$ (bit $k$) và $(i+1,k)$ với $k\le j$ (bit $k$). Chẳng hạn thanh ngang $1\times 3$ gồm $(i,j),(i,j+1),(i,j+2)$ vẫn mã hoá được bằng cách bật bit $j+1$ và $j+2$ (cần cả hai bit đang bằng 0). Ví dụ hai hướng của gạch chữ L (tromino) thoả điều kiện này:

 hướng A: (i,j),(i,j+1),(i+1,j)       hướng B: (i,j),(i+1,j-1),(i+1,j)
      [@][#]                                  [@]
      [#]                                  [#][#]

// placed next to the other tile branches, when (i,j) is empty
// L type A: (i,j), (i,j+1), (i+1,j)
if (i + 1 < n && j + 1 < m && !(mask >> (j + 1) & 1)) {
    int nm = mask | (1 << j) | (1 << (j + 1)); // bit j: (i+1,j), bit j+1: (i,j+1)
    ndp[nm] = (ndp[nm] + ways) % MOD;
}
// L type B: (i,j), (i+1,j-1), (i+1,j)
if (i + 1 < n && j >= 1 && !(mask >> (j - 1) & 1)) { // bit j-1 now means (i+1,j-1)
    int nm = mask | (1 << (j - 1)) | (1 << j);
    ndp[nm] = (ndp[nm] + ways) % MOD;
}

Đã kiểm tra: domino cộng hai hướng L này, so với quay lui trên mọi lưới tới $5\times 5$, khớp toàn bộ (ví dụ $2\times 3\to 4$, $3\times 4\to 25$, $4\times 4\to 112$).

Bẫy: gạch chạm ô $(i+1,j+1)$. Gạch vuông $2\times 2$, cùng hai hướng L còn lại $(i,j),(i,j+1),(i+1,j+1)$ và $(i,j),(i+1,j),(i+1,j+1)$, đều chiếm ô $(i+1,j+1)$. Ô này không có bit nào trên biên lúc đang ở $(i,j)$: bit $j+1$ vẫn là ô $(i,j+1)$ của hàng hiện tại. Viết "bật bit $j$ và bit $j+1$" cho gạch $2\times 2$ là sai: ô $(i+1,j+1)$ không bao giờ được đánh dấu, và khi xét $(i,j+1)$ bit đó chỉ bị tắt đi (thử thì $2\times 2$ ra 2 thay vì 3, $3\times 3$ ra 2 thay vì 0). Muốn dùng các gạch này phải làm giàu biên, ví dụ cho mỗi vị trí giá trị 2 nghĩa là "ô này đã bị phủ và ô ngay dưới nó cũng đã bị phủ" (khi tắt vị trí đó ở ô $(i,j+1)$ thì đặt lại thành 1 cho hàng dưới), hoặc chuyển trạng thái theo cả hàng như DP bitmask theo cột. Cách dùng giá trị 2 cho domino cộng gạch $2\times 2$ đã được so với quay lui tới $5\times 5$: $2\times 2\to 3$, $3\times 3\to 0$, $4\times 4\to 165$. Luôn so với quay lui trên lưới nhỏ khi thêm loại gạch mới.

Với lưới có ô cấm blocked[i][j] (bài chỉ phủ các ô trống):

• Ô $(i,j)$ bị cấm: chỉ chuyển khi bit $j=0$ (không gạch nào được đè lên nó), giữ bit $j=0$ và đi tiếp.
• Gạch dọc cần thêm !blocked[i+1][j]; gạch ngang cần thêm !blocked[i][j+1].

Plug DP (DP theo liên thông)

Phần này giải bài kinh điển (kiểu bài "Formula 1"): cho lưới $n\times m$ ($n,m\le 12$) gồm ô trống . và ô cấm *, đếm số chu trình Hamilton đi qua mọi ô trống đúng một lần, mỗi bước sang ô kề cạnh. Hai chu trình chỉ khác chiều đi được tính là một. Tương đương: đếm số cách chọn cạnh sao cho mỗi ô trống có đúng 2 cạnh và các cạnh tạo thành một vòng.

Các bài cùng họ: "nối ống" (mỗi ô là một đoạn ống, các ống phải nối thành một vòng kín hoặc nhiều vòng), đếm/tối ưu một đường đi qua mọi ô, chọn nhiều đường S đến T rời nhau trên lưới hẹp (như voi19_robot).

Trạng thái

Duyệt ô theo hàng, trong hàng từ trái sang phải. Biên gồm $m+1$ plug:

Đang xét ô (i, j):

   p0   p1  ...  p_{j-1}  |  p_{j+1}  p_{j+2} ... p_m     <- cạnh dọc bị biên cắt
   (cạnh xuống từ         |  (cạnh xuống từ hàng i-1, cột j..m-1)
    hàng i, cột 0..j-1)   |
                  p_j = cạnh NGANG đi từ (i, j-1) sang (i, j)

• $p_j$ = plug trái $L$ của ô $(i,j)$, $p_{j+1}$ = plug trên $U$.
• Sau khi xử lý, $p_j$ trở thành cạnh đi xuống từ $(i,j)$, $p_{j+1}$ trở thành cạnh đi sang phải từ $(i,j)$.
• Hết một hàng: $p_m$ (cạnh sang phải của ô cuối hàng) phải trống; dịch toàn bộ plug lên một chỉ số (state << 2) để $p_0$ trở thành cạnh trái (luôn trống) của ô đầu hàng mới.

Mỗi plug có 3 giá trị: 0 (không có cạnh), 1 = ( (đầu trái của một đoạn), 2 = ) (đầu phải). Gói $m+1\le 13$ plug vào một số 64 bit, mỗi plug 2 bit.

Hai cách mã hoá liên thông

Nhãn tối thiểu: sau mỗi lần gộp hai thành phần, đổi nhãn sao cho duyệt từ trái sang phải, nhãn mới xuất hiện theo thứ tự $1,2,3,\dots$ Ví dụ 3 0 1 3 1 chuẩn hoá thành 1 0 2 1 2. Không chuẩn hoá thì cùng một trạng thái mang nhiều tên khác nhau, số trạng thái phình to và DP không gộp được. Cách này tổng quát hơn nhưng mỗi plug tốn 3 đến 4 bit và phải chuẩn hoá $O(m)$ ở mỗi chuyển trạng thái. Với chu trình/đường đi, dãy ngoặc gọn và nhanh hơn, nên code dưới đây dùng dãy ngoặc.

Các trường hợp tại một ô trống

Gọi $L=p_j$, $U=p_{j+1}$. Ô trống cần đúng 2 cạnh trong 4 hướng (trái, trên, phải, xuống).

1) L=0, U=0: ô chưa có cạnh nào -> phải mở 2 cạnh mới: xuống và phải.
            Đây là một đoạn mới:  p_j = '(' ,  p_{j+1} = ')'
                 [ ]--->
                  |
                  v
2) Đúng một plug (L hoặc U = x): ô đã có 1 cạnh -> đi tiếp đúng 1 cạnh:
            xuống:     p_j = x,  p_{j+1} = 0
            sang phải: p_j = 0,  p_{j+1} = x
3) Hai plug: ô đã đủ 2 cạnh -> không mở thêm, p_j = p_{j+1} = 0, và nối hai đoạn:
   a) L='(', U='(' : hai đoạn  (L ... a)  và  (U ... b)  với  b < a  (lồng nhau).
                    Nối L với U: đầu b trở thành '(' của đoạn mới (b ... a).
   b) L=')', U=')' : đối xứng: đầu '(' ghép cặp với L trở thành ')'.
   c) L=')', U='(' : đoạn (x ... L) và (U ... y): nối lại thành (x ... y),
                    x vẫn là '(' và y vẫn là ')', không phải sửa gì.
   d) L='(', U=')' : L và U là HAI ĐẦU CỦA CÙNG MỘT ĐOẠN (ngoặc liền nhau) -> khép chu trình.
                    Chỉ hợp lệ khi đây là ô trống cuối cùng và không còn plug nào khác.

Vì sao ở 3d, ( tại $p_j$ và ) tại $p_{j+1}$ chắc chắn là một cặp? Hai vị trí kề nhau, giữa chúng không có ngoặc nào, nên theo quy tắc ghép ngoặc chúng khớp với nhau. Khép vòng ở bất kỳ ô nào khác ô cuối sẽ để lại ô trống chưa đi, hoặc tạo nhiều vòng rời nhau: phải loại.

Ô cấm: chỉ đi tiếp khi $L=U=0$, giữ nguyên trạng thái. Ngoài ra khi đi xuống hoặc sang phải phải kiểm tra ô đích tồn tại và không bị cấm; nhờ vậy không bao giờ có plug chĩa vào ô cấm hay ra ngoài lưới.

Vì sao cần bảng băm

Mỗi plug có 3 giá trị nên có tối đa $3^{m+1}$ dãy; mảng đánh chỉ số trực tiếp theo 2 bit mỗi plug cần $4^{m+1}=2^{26}$ phần tử với $m=12$ (hơn 500MB nếu lưu long long). Nhưng phần lớn dãy không phải dãy ngoặc hợp lệ và không bao giờ xuất hiện. Đo trên lưới trống:

Vì vậy ta lưu các trạng thái đang sống trong một bảng băm (địa chỉ mở, dò tuyến tính) cùng danh sách ô đã dùng để duyệt và xoá nhanh. std::unordered_map cũng chạy được nhưng chậm hơn vài lần.

Code C++: đếm chu trình Hamilton trên lưới có ô cấm

Input: dòng đầu $n,m$; $n$ dòng tiếp theo, mỗi dòng $m$ ký tự (. trống, * cấm). Output: số chu trình Hamilton qua mọi ô trống (lưới không có ô trống thì in 0).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Open-addressing hash map: state -> count. Only reachable states are stored.
struct StateMap {
    static const int CAP = 1 << 19;          // table size (power of two), far above the real state count
    vector<ll> key, val;
    vector<int> used;                       // list of occupied slots
    StateMap() : key(CAP, -1), val(CAP, 0) {}
    void clear() {
        for (int s : used) key[s] = -1, val[s] = 0;
        used.clear();
    }
    void add(ll k, ll v) {
        int s = (int)((k * 0x9E3779B97F4A7C15ULL) >> 45) & (CAP - 1);
        while (key[s] != -1 && key[s] != k) s = (s + 1) & (CAP - 1);
        if (key[s] == -1) key[s] = k, used.push_back(s);
        val[s] += v;
    }
};

int n, m;
vector<string> g;

// plug p occupies bits [2p, 2p+1]: 0 = none, 1 = '(' , 2 = ')'
inline int get(ll st, int p) { return (st >> (2 * p)) & 3; }
inline ll setp(ll st, int p, ll v) { return (st & ~(3LL << (2 * p))) | (v << (2 * p)); }

bool freeCell(int i, int j) { return i >= 0 && i < n && j >= 0 && j < m && g[i][j] == '.'; }

int main() {
    cin >> n >> m;
    g.resize(n);
    for (auto &row : g) cin >> row;

    // last free cell in row-major order: the only place a cycle may close
    int ei = -1, ej = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '.') ei = i, ej = j;
    if (ei == -1) { cout << 0 << "\n"; return 0; }

    StateMap A, B;
    StateMap *cur = &A, *nxt = &B;
    cur->add(0, 1);
    ll answer = 0;

    for (int i = 0; i < n; i++) {
        // new row: shift every plug one position right (plug m must be empty)
        nxt->clear();
        for (int s : cur->used) {
            ll st = cur->key[s];
            if (get(st, m) != 0) continue;
            nxt->add(st << 2, cur->val[s]);
        }
        swap(cur, nxt);

        for (int j = 0; j < m; j++) {
            nxt->clear();
            for (int s : cur->used) {
                ll st = cur->key[s], ways = cur->val[s];
                int L = get(st, j), U = get(st, j + 1); // left plug, up plug
                ll base = setp(setp(st, j, 0), j + 1, 0);

                if (g[i][j] != '.') {                 // blocked cell: no edge may enter
                    if (L == 0 && U == 0) nxt->add(st, ways);
                    continue;
                }
                bool down = freeCell(i + 1, j), right = freeCell(i, j + 1);

                if (L == 0 && U == 0) {               // open a new segment: down '(' and right ')'
                    if (down && right) nxt->add(setp(setp(base, j, 1), j + 1, 2), ways);
                } else if (L == 0 || U == 0) {        // one plug: extend it down or right
                    int x = L + U;
                    if (down)  nxt->add(setp(base, j, x), ways);
                    if (right) nxt->add(setp(base, j + 1, x), ways);
                } else if (L == 1 && U == 1) {        // "((": partner ')' of U becomes '('
                    int depth = 0;
                    for (int p = j + 1; p <= m; p++) {
                        int c = get(st, p);
                        if (c == 1) depth++;
                        else if (c == 2 && --depth == 0) { nxt->add(setp(base, p, 1), ways); break; }
                    }
                } else if (L == 2 && U == 2) {        // "))": partner '(' of L becomes ')'
                    int depth = 0;
                    for (int p = j; p >= 0; p--) {
                        int c = get(st, p);
                        if (c == 2) depth++;
                        else if (c == 1 && --depth == 0) { nxt->add(setp(base, p, 2), ways); break; }
                    }
                } else if (L == 2 && U == 1) {        // ")(": join two segments, partners stay
                    nxt->add(base, ways);
                } else {                              // L == '(' and U == ')': closes a cycle
                    if (i == ei && j == ej && base == 0) answer += ways;
                }
            }
            swap(cur, nxt);
        }
    }
    cout << answer << "\n";
}

Kiểm tra: code đã được so khớp với một chương trình quay lui (DFS đếm chu trình qua mọi ô trống, chia 2 cho hai chiều đi) trên 1900 lưới ngẫu nhiên kích thước tới $5\times 5$ có ô cấm, cùng lưới $6\times 6$ trống (1072 chu trình). Một số kết quả:

Kết quả $12\times 12$ vẫn vừa long long (khoảng $1.08·{10}^{18}<9.2·{10}^{18}$) và chạy dưới 0.1 giây.

Độ phức tạp

Lát domino:

Luôn xoay lưới để $m$ là chiều nhỏ: với $m\le 12$ thì $2^{12}=4096$, nên kể cả $n=1000$ cũng chỉ khoảng $5·{10}^7$ phép tính. Khi $n$ cực lớn (ví dụ ${10}^{18}$) và $m$ rất nhỏ, gộp một hàng thành ma trận chuyển $2^m\times 2^m$ rồi dùng lũy thừa ma trận: $O(2^{3m}\log n)$ (xem thêm DP nhân ma trận).

Plug DP: gọi $S$ là số trạng thái sống tối đa tại một bước.

$S$ bị chặn bởi số dãy ngoặc hợp lệ có xen vị trí trống độ dài $m+1$ (số Motzkin $M_{m+1}$, với $m=12$ là $M_{13}=41835$), nhỏ hơn rất nhiều so với $3^{m+1}$ (13 943 so với 1 594 323 ở $m=12$). Ô cấm chỉ làm $S$ nhỏ đi. Với $12\times 12$: khoảng $144·14000·13\approx 2.6·{10}^7$ bước, rất nhanh. Code trên dùng bảng $2^{19}$ ô mỗi bảng, tổng khoảng 16MB.

⚠️ Lỗi thường gặp

• Quên modulo hoặc tràn số. Số cách lát tăng theo cấp số mũ; phải cộng dồn trong long long và lấy % MOD sau mỗi phép cộng. Ở plug DP không có modulo, kiểm tra đáp án lớn nhất (lưới toàn trống kích thước tối đa) còn vừa long long; nếu không, cần __int128 hoặc số lớn.
• Quy ước bit không nhất quán. Bit $j$ phải luôn là chính ô đang xét, bit $<j$ là hàng dưới, bit $>j$ là hàng hiện tại. Trộn hai quy ước (lúc coi bit $j$ là ô hàng trên, lúc là ô hàng dưới) làm lệch toàn bộ chuyển trạng thái. Triệu chứng: đáp số $2\times 2$ không ra 2. Luôn thử $2\times 2=2$, $2\times 3=3$, $3\times 4=11$ trước khi nộp.
• Đặt gạch thò ra ngoài lưới hoặc chồng gạch. Gạch dọc cần i + 1 < n; gạch ngang cần j + 1 < m và bit $j+1=0$ (ô bên phải có thể đã bị gạch dọc từ hàng trên chiếm). Thiếu một trong các kiểm tra này thì đáp số lớn hơn thực tế.
• Gạch chạm ô $(i+1,j+1)$ với biên 1 bit/cột. Gạch $2\times 2$ hay chữ L có ô ở $(i+1,j+1)$ không mã hoá được bằng cách bật bit $j$ và $j+1$: bit $j+1$ vẫn là ô $(i,j+1)$ của hàng hiện tại, nên ô $(i+1,j+1)$ bị bỏ quên và đáp số sai mà không báo lỗi. Xem cách làm giàu biên ở mục Mở rộng.
• Lấy sai trạng thái kết thúc. Đáp án là dp[0] sau khi đi hết toàn bộ ô. Đọc đáp án ở dp[mask] với mask != 0, hoặc giữa chừng, đều sai.
• Không xoay lưới khi $m>n$. $2^m$ quyết định tốc độ; lưới $1000\times 10$ mà lấy $m=1000$ thì không chạy nổi. Bài cnttiling cho chiều nhỏ là $n$, nên phải swap.
• Cập nhật dp tại chỗ. Ghi vào ndp (hoặc bảng băm thứ hai) rồi mới đổi vai; sửa ngay trên mảng đang duyệt sẽ trộn trạng thái của hai bước khác nhau.
• Plug DP: khép chu trình sớm. Trường hợp L='(' , U=')' chỉ được cộng vào đáp án tại ô trống cuối cùng và khi mọi plug khác đều trống. Cho phép khép ở ô khác sẽ đếm cả cấu hình nhiều vòng rời nhau (bài "nối ống thành nhiều vòng" thì ngược lại, được phép khép ở bất cứ đâu). Ô trống cuối phải tính theo thứ tự duyệt, bỏ qua các ô cấm ở cuối lưới.
• Plug DP: quên kiểm tra plug $p_m$ khi sang hàng. Trước khi dịch state << 2, plug $p_m$ (cạnh sang phải của ô cuối hàng) phải trống; nếu không, sau khi dịch nó rơi vào vị trí $m+1$ nằm ngoài biên, trạng thái sai mà không báo lỗi. Code trên còn chặn sớm bằng freeCell(i, j+1).
• Plug DP: nhầm hướng tìm ngoặc ghép cặp. Với (( phải tìm ) khớp với U về phía phải (bắt đầu từ $p_{j+1}$), với )) tìm ( khớp với L về phía trái (bắt đầu từ $p_j$). Tìm sai phía hoặc bắt đầu sai vị trí cho dãy ngoặc hỏng mà không báo lỗi. Cách phát hiện: so với quay lui trên lưới nhỏ như đã làm ở trên.
• Bảng băm đầy hoặc quá nhỏ. Bảng địa chỉ mở phải lớn hơn hẳn số trạng thái (hệ số tải dưới 0.5); nếu đầy, vòng dò tuyến tính chạy mãi. Đồng thời đừng memset cả bảng ở mỗi ô: xoá theo danh sách used như code trên, nếu không chi phí xoá $O(\text{CAP})$ mỗi ô sẽ lấn át phần DP.

Biến thể / Mở rộng

• Tô màu / gán nhãn lưới với ràng buộc lân cận: biên mang màu của $m$ ô thay vì 1 bit, trạng thái thành $K^m$. Mỗi ô chỉ cần biết màu ô trái (vị trí $j-1$ của biên) và ô trên (vị trí $j$), nên vẫn chuyển từng ô trong $O(K)$.
• Gạch cao hơn 2 ô (thanh dọc $3\times 1$, hoặc thanh $1\times 3$ được phép xoay, hình chữ L lớn): biên cần nhớ nhiều hơn một hàng, mỗi vị trí lưu "còn bao nhiêu ô bị chiếm phía dưới" (số trạng thái $3^m$ hoặc hơn).
• Một đường đi qua mọi ô (đường Hamilton), hoặc đường nối S với T: ngoài ( và ) cần thêm loại plug thứ tư là đầu đơn (đoạn có một đầu đã cố định ở S, T hoặc đầu mút tự do). Số đầu đơn còn mở cũng thành một phần của trạng thái (tối đa 2 với một đường).
• Plug DP tối ưu: thay += bằng max/min để tìm chu trình có tổng trọng số ô lớn nhất, hoặc cho phép bỏ qua ô (ô không có cạnh nào) để tìm vòng kín bất kỳ.
• Nhiều vòng rời nhau (bài "nối ống" phủ lưới bằng các vòng): không cần nhớ liên thông nữa, chỉ cần bit "có plug hay không", quay về broken profile $2^{m+1}$ trạng thái thường.
• Liên thông tổng quát (tô đen trắng sao cho mỗi màu liên thông, đếm cây khung trên lưới): dùng nhãn tối thiểu thay dãy ngoặc, có thể cần DSU nhỏ trên $m$ nhãn để gộp.
• Liên hệ: DP bitmask (chuyển theo cột, mask là tập con) và bảng băm (cài đặt bảng địa chỉ mở).

Bài tập luyện

Luyện kỹ thuật

• Đường Đi Hamilton (grazing) (Học việc) đếm đường Hamilton từ góc $(1,1)$ tới góc $(5,5)$ trên lưới $5\times 5$ có ô chặn. Lưới nhỏ nên quay lui là đủ và bài không bắt buộc plug DP; hãy dùng nó để kiểm tra bản plug DP của bạn cho đường đi (hai đầu mút cố định là plug đầu đơn).
• Lát bảng 3 x n (fillshape) (Nghiệp dư) đếm cách lát $3\times n$ bằng mảnh chữ L: có công thức đóng, nhưng là bài khởi động tốt để viết broken profile với gạch không phải domino. Đặt lưới thành $n$ hàng, $m=3$ cột và duyệt theo hàng như trên trang này: trong bốn hướng xoay chữ L, hai hướng dùng được ngay với biên 1 bit/cột (hướng A, B ở mục Mở rộng), còn hai hướng chạm ô $(i+1,j+1)$ thì không viết được bằng cách bật bit (đúng cái bẫy đã nêu ở trên), cần biên giàu hơn hoặc chuyển theo cả hàng.
• Đếm Cách Lát Gạch (cnttiling) (Kỳ cựu) đúng bài lát domino ở trên với $n\le 10$, $m\le 1000$: nhớ xoay để chiều nhỏ làm độ dài biên.
• Đội Hợp Xướng Hogwarts (choirform) (Kỳ cựu) gán mỗi ô một trong $K\le 4$ loại giọng để tối thiểu tổng bất hoà giữa các ô kề, $M\le 7$: biên mang màu của $M$ ô ($K^M\le 16384$ trạng thái), DP tối ưu thay vì đếm.
• Ô không có nhện (spidfree) (Kỳ cựu) mỗi con nhện đứng yên hoặc bước sang ô kề, cần giữ lại ít ô có nhện nhất: tức là tìm tập thống trị nhỏ nhất trên lưới $n\times m$ với $n·m\le 40$ (chiều nhỏ $\le 6$). Duyệt theo hàng với biên nhớ cho mỗi cột hai thông tin "ô hàng trên đã được chọn chưa" và "ô hàng trên đã được thống trị chưa"; khi xét ô $(i,j)$ mà ô $(i-1,j)$ vẫn chưa được thống trị thì bắt buộc phải chọn $(i,j)$, vì đó là cơ hội cuối. DP tối ưu (min), không phải đếm.

Hiện chưa tìm thấy trong pool CTOJ bài đếm chu trình Hamilton trên lưới kích thước lớn (kiểu Formula 1); bạn có thể tự kiểm tra code plug DP ở trên bằng các giá trị trong bảng kiểm tra.

Đề VOI

• Thử nghiệm robot (voi19_robot) (Chuyên gia) VOI 2019: lưới chỉ có 3 hàng và $n\le {10}^5$ cột, cần chọn nhiều đường S đến T rời nhau nhất. Duyệt theo cột, biên chỉ có vài plug; mỗi plug cần nhớ đầu kia của đoạn đang dở là S, T hay một plug khác (như cặp ngoặc), cộng một cờ nhỏ cho ràng buộc về ô kém chất lượng. Cẩn thận các phép ghép nào tạo chu trình hoặc tạo đường không hợp lệ.

Trong các đề VOI có trong pool CTOJ, đây là bài duy nhất dùng broken profile/plug DP. Ngoài pool còn có bài VOI 2006 voi06_select (lưới $4\times n$) mà lời giải là DP mặt nạ theo cột với 8 mặt nạ, cũng là một dạng profile DP theo cột, nhưng bài này chưa có trong pool nên không gắn link được.