Broken Profile DP

Biên gãy theo từng ô

Lát bảng $n \times m$ bằng domino, $n$ nhỏ. Duyệt từng cột từ trái sang, trong mỗi cột từ trên xuống. Khi đang ở ô $(r, c)$, biên đi dọc cột $c$ từ hàng $r$ xuống, rồi gãy sang cột $c + 1$ cho các hàng phía trên $r$. Bit $j$ của mặt nạ cho biết ô trên biên ở hàng $j$ đã bị phủ chưa: với $j \ge r$ đó là ô $(j, c)$, với $j < r$ đó là ô $(j, c + 1)$, bị phủ bởi domino ngang đặt từ cột $c$.

Tại ô $(r, c)$ với bit $r$:

• Bit $r$ đã bật: ô đã phủ, không làm gì; bit $r$ chuyển sang nói về ô $(r, c + 1)$, chưa phủ, nên tắt.
• Bit $r$ tắt: đặt domino ngang sang $(r, c + 1)$, bật bit $r$; hoặc đặt domino dọc xuống $(r + 1, c)$ nếu còn hàng và bit $r + 1$ tắt, khi đó bật bit $r + 1$ còn bit $r$ tắt.

Mỗi ô có $2^n$ trạng thái và tối đa hai chuyển tiếp: $O(nm 2^n)$. Làm theo cả cột thì mỗi cặp mặt nạ (cột trước, cột sau) phải kiểm riêng, $O(m 4^n)$.

Ví dụLát Kín Bảng Chữ Nhật

Đề. Bảng $n \le 10$ hàng, $m \le 1000$ cột. Đếm số cách lát kín bằng domino, modulo $10^9 + 7$.

Lời giải. Duyệt ô theo từng cột, trong cột theo từng hàng. Mặt nạ s có $n$ bit: bit $r$ cho biết ô ở hàng $r$ của cột đang xét đã bị phủ sẵn chưa, bởi domino ngang từ cột trước hay domino dọc từ ô ngay trên.

Bước 1: ô đã bị phủ. Không đặt gì; xóa bit $r$, vì từ giờ bit đó nói về ô hàng $r$ của cột $c + 1$.

if (s >> r & 1) nd[s ^ (1 << r)] = (nd[s ^ (1 << r)] + v) % MOD;

Bước 2: ô còn trống. Đặt domino ngang sang cột sau thì bật bit $r$ (cho cột $c + 1$), chỉ khi còn cột sau. Đặt domino dọc xuống ô $(r + 1, c)$ thì bật bit $r + 1$, chỉ khi ô đó cũng còn trống.

else {
    if (c + 1 < m) nd[s | (1 << r)] = (nd[s | (1 << r)] + v) % MOD;
    if (r + 1 < n && !(s >> (r + 1) & 1)) nd[s | (1 << (r + 1))] = (nd[s | (1 << (r + 1))] + v) % MOD;
}

Bước 3: chuyển bảng. Mỗi ô xóa nd, chuyển từ dp, rồi chép lại vào dp. Sau ô cuối cùng, dp[0] là số cách không ô nào của cột ảo $m + 1$ bị phủ, tức lát vừa khít.

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

const ll MOD = 1e9 + 7;
ll n, m, dp[1 << 10], nd[1 << 10];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ll full = 1 << n;
    dp[0] = 1;
    for (ll c = 0; c < m; c++)
        for (ll r = 0; r < n; r++) {
            for (ll s = 0; s < full; s++) nd[s] = 0;
            for (ll s = 0; s < full; s++) {
                if (!dp[s]) continue;
                ll v = dp[s];
                if (s >> r & 1) nd[s ^ (1 << r)] = (nd[s ^ (1 << r)] + v) % MOD;
                else {
                    if (c + 1 < m) nd[s | (1 << r)] = (nd[s | (1 << r)] + v) % MOD;
                    if (r + 1 < n && !(s >> (r + 1) & 1)) nd[s | (1 << (r + 1))] = (nd[s | (1 << (r + 1))] + v) % MOD;
                }
            }
            for (ll s = 0; s < full; s++) dp[s] = nd[s];
        }
    cout << dp[0] << '\n';
}

ChạyInput2 3

Output3

$n \cdot m \cdot 2^n \approx 10^7$ bước.

Chênh lệch giữa hai cách duyệt lộ rõ khi $n$ lớn:

Biên gãy từng ô nhanh hơn cách thử mọi cặp mặt nạ cỡ 26 lần, và mỗi hàng thêm vào nhân khoảng cách lên hai lần.

Cả hàng làm trạng thái

Khi ràng buộc chỉ nối hai hàng liền nhau (không hai ô chọn chung cạnh, không ngồi chéo), lấy cả hàng làm mặt nạ: $dp[i][s]$ là số cách cho $i$ hàng đầu với hàng $i$ chọn tập $s$. Chuyển tiếp duyệt mọi cặp $(s', s)$ của hai hàng liền nhau.

Trước hết lọc các mặt nạ tự hợp lệ trong một hàng: không hai bit kề nhau thì với $m = 12$ chỉ còn 377 mặt nạ trong 4096. Điều kiện giữa hai hàng thường là một phép bit: không chung cạnh dọc là s & s2 == 0, không chéo là (s << 1) & s2 == 0 và (s >> 1) & s2 == 0.

Ví dụChọn Ô Không Chung Cạnh

Đề. Bảng $N, M \le 12$, mỗi ô được phép chọn hoặc không. Đếm số tập ô được phép, không hai ô nào chung cạnh, modulo $10^8$.

Lời giải. Quy hoạch động theo hàng, trạng thái là mặt nạ các ô chọn ở hàng vừa xét. Hai ô trong một hàng không được kề nhau; hai hàng liền nhau không được chọn cùng cột.

Bước 1: mặt nạ ô được phép. fr[i] bật bit $j$ khi ô $(i, j)$ được chọn.

if (x) fr[i] |= 1 << j;

Bước 2: lọc mặt nạ một hàng. Mặt nạ không có hai bit kề khi s & (s << 1) bằng 0. Với $m = 12$ chỉ còn 377 mặt nạ; lọc một lần, dùng cho mọi hàng.

for (ll s = 0; s < (1 << m); s++)
    if (!(s & (s << 1))) ok.push_back(s);

Bước 3: chuyển hàng. Mặt nạ $s$ phải nằm gọn trong fr[i]; cộng dp của mọi mặt nạ $t$ ở hàng trước không giao $s$. dp[0] = 1 trước hàng đầu, coi như có một hàng rỗng phía trên.

for (ll s : ok) {
    if ((s & fr[i]) != s) continue;
    for (ll t : ok)
        if (!(s & t) && dp[t]) nd[s] = (nd[s] + dp[t]) % MOD;
}

Đáp án cộng mọi trạng thái của hàng cuối, kể cả mặt nạ rỗng (tập không chọn ô nào cũng được đếm).

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

const ll MOD = 1e8;
ll n, m, fr[15], dp[1 << 12], nd[1 << 12];
vector<ll> ok;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < m; j++) {
            ll x;
            cin >> x;
            if (x) fr[i] |= 1 << j;
        }
    for (ll s = 0; s < (1 << m); s++)
        if (!(s & (s << 1))) ok.push_back(s);
    dp[0] = 1;
    for (ll i = 0; i < n; i++) {
        for (ll s : ok) nd[s] = 0;
        for (ll s : ok) {
            if ((s & fr[i]) != s) continue;
            for (ll t : ok)
                if (!(s & t) && dp[t]) nd[s] = (nd[s] + dp[t]) % MOD;
        }
        for (ll s : ok) dp[s] = nd[s];
    }
    ll ans = 0;
    for (ll s : ok) ans = (ans + dp[s]) % MOD;
    cout << ans << '\n';
}

ChạyInput1 3
1 1 1

Output5

Độ phức tạp: $O(N \cdot 377^2) \approx 1{,}7 \cdot 10^6$.

Ràng buộc hai hàng

Nếu ràng buộc nối hàng $i$ với cả hàng $i - 1$ và $i - 2$ (trạm cách nhau tới 2 ô theo cột), trạng thái phải giữ hai hàng gần nhất: $dp[i][a][b]$ với $a$ là mặt nạ hàng $i$, $b$ hàng $i - 1$. Chuyển tiếp thử mặt nạ $c$ cho hàng $i - 2$ cũ: điều kiện là $a, b, c$ đôi một không giao. Số mặt nạ tự hợp lệ rất nhỏ (không hai bit trong khoảng cách 2: với $m = 10$ chỉ 60), nên $O(N \cdot 60^3)$ vẫn nhanh. Lọc trước cũng giúp bỏ các mặt nạ đặt trạm lên ô cấm.

Ví dụTrạm Tín Hiệu Trên Lưới

Đề. Lưới $N \le 100$ hàng, $M \le 10$ cột, ô P đặt được trạm. Hai trạm cùng hàng hay cùng cột cách nhau 1 hoặc 2 ô thì nhiễu nhau. Đặt nhiều trạm nhất.

Lời giải. Trạm ở hàng $i$ nhiễu với trạm cùng cột ở hàng $i - 1$ và $i - 2$, nên trạng thái phải nhớ mặt nạ của cả hai hàng gần nhất.

Bước 1: mặt nạ một hàng. Không có hai trạm cách nhau 1 hay 2 ô: s & (s << 1) và s & (s << 2) đều bằng 0. Với $m = 10$ chỉ còn 60 mặt nạ, nên trạng thái dùng chỉ số trong danh sách ok thay cho chính mặt nạ.

for (ll s = 0; s < (1 << m); s++)
    if (!(s & (s << 1)) && !(s & (s << 2))) ok.push_back(s);

Bước 2: trạng thái. dp[a][b] là số trạm lớn nhất khi hàng hiện tại dùng ok[a], hàng trước dùng ok[b]; $-1$ là trạng thái không tồn tại. Bắt đầu với hai hàng rỗng: dp[0][0] = 0.

Bước 3: thêm hàng mới $x$. Phải nằm trong ô P, không giao hàng ngay trên ($a$) và hàng trên nữa ($b$). Trạng thái mới là $(x, a)$, cộng số trạm của $x$.

for (ll x = 0; x < k; x++) {
    if ((ok[x] & fr[i]) != ok[x]) continue;
    ll c = __builtin_popcountll(ok[x]);
    for (ll a = 0; a < k; a++) {
        if (ok[x] & ok[a]) continue;
        for (ll b = 0; b < k; b++) {
            if (dp[a][b] < 0 || (ok[x] & ok[b])) continue;
            nd[x][a] = max(nd[x][a], dp[a][b] + c);
        }
    }
}

Đáp án là lớn nhất trên mọi trạng thái sau hàng cuối.

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

ll n, m, fr[105], dp[65][65], nd[65][65];
vector<ll> ok;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < m; j++)
            if (s[j] == 'P') fr[i] |= 1 << j;
    }
    for (ll s = 0; s < (1 << m); s++)
        if (!(s & (s << 1)) && !(s & (s << 2))) ok.push_back(s);
    ll k = ok.size();
    for (ll a = 0; a < k; a++)
        for (ll b = 0; b < k; b++) dp[a][b] = -1;
    dp[0][0] = 0;
    for (ll i = 0; i < n; i++) {
        for (ll a = 0; a < k; a++)
            for (ll b = 0; b < k; b++) nd[a][b] = -1;
        for (ll x = 0; x < k; x++) {
            if ((ok[x] & fr[i]) != ok[x]) continue;
            ll c = __builtin_popcountll(ok[x]);
            for (ll a = 0; a < k; a++) {
                if (ok[x] & ok[a]) continue;
                for (ll b = 0; b < k; b++) {
                    if (dp[a][b] < 0 || (ok[x] & ok[b])) continue;
                    nd[x][a] = max(nd[x][a], dp[a][b] + c);
                }
            }
        }
        for (ll a = 0; a < k; a++)
            for (ll b = 0; b < k; b++) dp[a][b] = nd[a][b];
    }
    ll ans = 0;
    for (ll a = 0; a < k; a++)
        for (ll b = 0; b < k; b++) ans = max(ans, dp[a][b]);
    cout << ans << '\n';
}

ChạyInput3 5
PHPHP
PPPPP
HPHPH

Output4

$N \cdot 60^3 \approx 2{,}2 \cdot 10^7$ bước.

Bit mang thông tin

Bit trên biên không chỉ nói “đã phủ hay chưa”; nó có thể mang bất kỳ thông tin nhị phân nào cần cho ô kế tiếp. Phủ sàn bằng ít thanh thẳng nhất: mỗi ô thuộc một thanh ngang hoặc một thanh dọc, và một thanh mới tốn 1 khi không nối tiếp được thanh cùng hướng ở ô bên cạnh. Duyệt theo hàng, bit $j$ là “ô gần nhất đã xét ở cột $j$ có thuộc thanh dọc không”. Ô $(r, c)$ đi dọc thì miễn phí nếu ô trên là sàn và bit $c$ bật; đi ngang thì miễn phí nếu ô trái là sàn và bit $c - 1$ (đã cập nhật ở hàng này) tắt. Ô chắn đặt bit về 0 và không tốn gì.

Ví dụPhủ Sàn Bằng Các Thanh Thẳng

Đề. Bảng $N, M \le 10$ có ô sàn . và cột chắn #. Phủ mọi ô sàn bằng các thanh thẳng $1 \times K$ hoặc $K \times 1$ không chồng nhau, dùng ít thanh nhất.

Lời giải. Mỗi ô sàn thuộc một thanh ngang hoặc một thanh dọc. Số thanh bằng số ô “mở đầu” một thanh: ô dọc mà ô trên không đi dọc, ô ngang mà ô trái không đi ngang. Duyệt ô theo hàng, mặt nạ s nhớ hướng của $m$ ô gần nhất: bit $j$ bật khi ô gần nhất đã xét ở cột $j$ đi dọc (với cột $< c$ là ô ở hàng hiện tại, với cột $\ge c$ là ô ở hàng trên). $dp[s]$ là số thanh ít nhất.

Bước 1: ô chắn. Không thanh nào đi qua: xóa bit $c$, không tốn gì.

if (g[r][c] == '#') {
    ll t = s & ~(1LL << c);
    nd[t] = min(nd[t], v);
    continue;
}

Bước 2: ô sàn đi dọc. Miễn phí khi ô trên là sàn và cũng đi dọc (bit $c$ đang bật), ngược lại mở thanh mới tốn 1. Bật bit $c$.

ll up = r > 0 && g[r - 1][c] == '.' && (s >> c & 1);
ll t = s | (1LL << c);
nd[t] = min(nd[t], v + !up);

Bước 3: ô sàn đi ngang. Miễn phí khi ô trái là sàn và đi ngang (bit $c - 1$, đã cập nhật ở hàng này, đang tắt). Xóa bit $c$.

ll left = c > 0 && g[r][c - 1] == '.' && !(s >> (c - 1) & 1);
t = s & ~(1LL << c);
nd[t] = min(nd[t], v + !left);

Đáp án là nhỏ nhất trên mọi mặt nạ sau ô cuối; bảng không có ô sàn cho 0.

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

const ll INF = 1e18;
ll n, m, dp[1 << 10], nd[1 << 10];
string g[12];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 0; i < n; i++) cin >> g[i];
    ll full = 1 << m;
    for (ll s = 0; s < full; s++) dp[s] = INF;
    dp[0] = 0;
    for (ll r = 0; r < n; r++)
        for (ll c = 0; c < m; c++) {
            for (ll s = 0; s < full; s++) nd[s] = INF;
            for (ll s = 0; s < full; s++) {
                if (dp[s] == INF) continue;
                ll v = dp[s];
                if (g[r][c] == '#') {
                    ll t = s & ~(1LL << c);
                    nd[t] = min(nd[t], v);
                    continue;
                }
                ll up = r > 0 && g[r - 1][c] == '.' && (s >> c & 1);
                ll t = s | (1LL << c);
                nd[t] = min(nd[t], v + !up);
                ll left = c > 0 && g[r][c - 1] == '.' && !(s >> (c - 1) & 1);
                t = s & ~(1LL << c);
                nd[t] = min(nd[t], v + !left);
            }
            for (ll s = 0; s < full; s++) dp[s] = nd[s];
        }
    ll ans = INF;
    for (ll s = 0; s < full; s++) ans = min(ans, dp[s]);
    cout << ans << '\n';
}

ChạyInput2 2
..
..

Output2

$2^{10}$ trạng thái nhân 100 ô, khoảng $10^5$ bước.

Bảng rất dài

Khi chiều dài tới $10^{12}$, chuyển tiếp giữa hai cột liên tiếp giống hệt nhau ở mọi cột, nên là một ma trận $T$ kích thước $2^n \times 2^n$: $T[a][b]$ là số cách điền một cột khi các ô trong $a$ đã bị domino ngang từ cột trước chiếm và các ô trong $b$ bắt đầu domino ngang sang cột sau. Đáp án là $(T^W)[0][0]$, tính bằng lũy thừa nhị phân ma trận (bài 18) trong $O(8^n \log W)$. Mỗi ô $T[a][b]$ đếm cách phủ các ô còn trống trong cột bằng những miếng nằm gọn trong cột.

Ví dụLát Bảng Rất Dài

Đề. Bảng $H \le 6$ hàng, $W \le 10^{12}$ cột, lát bằng ô $1 \times 1$, domino ngang và domino dọc. Đếm số cách, modulo $998244353$.

Lời giải. $W$ tới $10^{12}$ nên không thể đi từng cột; nhưng mọi cột chuyển như nhau, nên dựng ma trận chuyển $T$ một lần rồi lũy thừa. Trạng thái giữa hai cột là mặt nạ các ô bị domino ngang nối qua.

Bước 1: ma trận chuyển. $a$ là các ô của cột bị domino ngang từ cột trước chiếm, $b$ là các ô bắt đầu domino ngang sang cột sau. $a$ và $b$ giao nhau thì $T[a][b] = 0$. Các ô còn lại chia thành các đoạn liền; đoạn dài $k$ phủ bằng ô đơn và domino dọc theo $f_k$ cách, với $f_0 = f_1 = 1$, $f_k = f_{k-1} + f_{k-2}$. Vòng r chạy tới $h$ (dư một ô) để chốt đoạn cuối.

for (ll a = 0; a < S; a++)
    for (ll b = 0; b < S; b++) {
        if (a & b) continue;
        ll ways = 1, run = 0;
        for (ll r = 0; r <= h; r++) {
            if (r < h && !((a | b) >> r & 1)) run++;
            else {
                ways *= f[run];
                run = 0;
            }
        }
        T[a][b] = ways % MOD;
    }

Bước 2: nhân ma trận. Ma trận $2^h \times 2^h$ theo mô-đun; bỏ qua phần tử 0 của a để nhanh hơn.

vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b) {
    vector<vector<ll>> c(S, vector<ll>(S, 0));
    for (ll i = 0; i < S; i++)
        for (ll k = 0; k < S; k++) {
            if (!a[i][k]) continue;
            for (ll j = 0; j < S; j++) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
        }
    return c;
}

Bước 3: lũy thừa nhị phân. R bắt đầu là ma trận đơn vị. $(T^W)[0][0]$ là số cách đi từ “không ô nào bị chiếm” trước cột đầu tới “không ô nào sang cột ảo” sau cột cuối.

for (; w; w >>= 1) {
    if (w & 1) R = mul(R, T);
    T = mul(T, T);
}

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

const ll MOD = 998244353;
ll h, w, S, f[10];
vector<vector<ll>> T;

vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b) {
    vector<vector<ll>> c(S, vector<ll>(S, 0));
    for (ll i = 0; i < S; i++)
        for (ll k = 0; k < S; k++) {
            if (!a[i][k]) continue;
            for (ll j = 0; j < S; j++) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
        }
    return c;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> h >> w;
    S = 1 << h;
    f[0] = f[1] = 1;
    for (ll k = 2; k < 10; k++) f[k] = f[k - 1] + f[k - 2];
    T.assign(S, vector<ll>(S, 0));
    for (ll a = 0; a < S; a++)
        for (ll b = 0; b < S; b++) {
            if (a & b) continue;
            ll ways = 1, run = 0;
            for (ll r = 0; r <= h; r++) {
                if (r < h && !((a | b) >> r & 1)) run++;
                else {
                    ways *= f[run];
                    run = 0;
                }
            }
            T[a][b] = ways % MOD;
        }
    vector<vector<ll>> R(S, vector<ll>(S, 0));
    for (ll i = 0; i < S; i++) R[i][i] = 1;
    for (; w; w >>= 1) {
        if (w & 1) R = mul(R, T);
        T = mul(T, T);
    }
    cout << R[0][0] << '\n';
}

ChạyInput2 2

Output7

Ước lượng phép tính: $64^3 \cdot \log_2 10^{12} \approx 10^7$ phép nhân.