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;
using 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';
}

Input2 3

Output3

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

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 có $\Theta(\varphi^m)$ mặt nạ, với $m = 12$ chỉ 377 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;
using 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';
}

Input1 3
1 1 1

Output5

$O(N \cdot 377^2) \approx 1{,}7 \cdot 10^6$.

Ràng buộc kéo dài 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;
using 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';
}

Input3 5
PHPHP
PPPPP
HPHPH

Output4

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

Thêm thông tin vào bit cho bài tối ưu

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;
using 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';
}

Input2 2
..
..

Output2

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

Bảng rất dài: nhân ma trận chuyển

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;
using 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';
}

Input2 2

Output7

$64^3 \cdot \log_2 10^{12} \approx 10^7$ phép nhân.