Lexicographic DP

Chia khối, giải mã

Các chuỗi hợp lệ sắp theo từ điển thì những chuỗi cùng ký tự đầu đứng liền nhau thành một khối, khối của ký tự nhỏ đứng trước. Gọi $cnt(c)$ là số chuỗi bắt đầu bằng $c$, tức số cách hoàn thiện phần còn lại sau khi đặt $c$.

Duyệt các ký tự $c$ từ nhỏ đến lớn. Nếu $K \le cnt(c)$ thì chuỗi cần tìm nằm trong khối của $c$: đặt $c$ và tìm chuỗi thứ $K$ trong khối đó. Ngược lại $K \gets K - cnt(c)$ và thử ký tự kế tiếp. Lặp lại cho từng vị trí. Mọi khó khăn dồn vào việc tính $cnt$.

Ví dụChuỗi aab, aba, baa

Đề. Có $A$ chữ a và $B$ chữ b với $A, B \le 30$. In chuỗi thứ $K$ theo thứ tự từ điển trong mọi chuỗi dùng đúng số chữ đó.

Lời giải. Còn $a$ chữ a và $b$ chữ b thì số chuỗi bắt đầu bằng a là $\binom{a + b - 1}{b}$: sắp $b$ chữ b vào $a + b - 1$ vị trí còn lại. $K$ không quá số đó thì đặt a, không thì trừ đi và đặt b. $\binom{60}{30} \approx 1{,}2 \cdot 10^{17}$ vẫn vừa ll; dựng bảng tổ hợp bằng tam giác Pascal để khỏi chia.

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

ll C[65][65];

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

    for (ll i = 0; i < 65; i++) {
        C[i][0] = 1;
        for (ll j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    ll a, b, k;
    cin >> a >> b >> k;
    string res;
    while (a + b > 0) {
        ll c = a ? C[a + b - 1][b] : 0;
        if (k <= c) {
            res += 'a';
            a--;
        } else {
            k -= c;
            res += 'b';
            b--;
        }
    }
    cout << res << '\n';
}

ChạyInput2 2 4

Outputbaab

Xếp hạng

Thứ hạng của một đối tượng $s$ là 1 cộng số đối tượng đứng trước nó. Một đối tượng $t$ đứng trước $s$ khi chúng giống nhau tới vị trí $i - 1$ rồi $t_i < s_i$. Vậy duyệt từng vị trí $i$, với mỗi ký tự $c < s_i$ đặt được ở đó, cộng số cách hoàn thiện.

Đây đúng là quá trình giải mã chạy ngược, nên hai hàm kiểm được lẫn nhau: giải mã thứ hạng vừa tính phải ra lại đối tượng ban đầu.

Với hoán vị của $1..n$: sau khi đã dùng các số ở vị trí trước, mỗi số chưa dùng nhỏ hơn $s_i$ mở một khối gồm $(n - i)!$ hoán vị. Đó là khai triển Cantor: thứ hạng là $1 + \sum_i c_i \cdot (n - i)!$ với $c_i$ là số số chưa dùng nhỏ hơn $s_i$.

Ví dụSố hiệu hoán vị

Đề. Một hoán vị của $1..n$ với $n \le 12$ (độ dài lấy từ dòng đầu) và một thứ hạng $p$. In thứ hạng của hoán vị đã cho và hoán vị ở thứ hạng $p$.

Lời giải. Xếp hạng bằng khai triển Cantor: ở vị trí $i$, mỗi số chưa dùng nhỏ hơn $a_i$ mở ra một khối $(n - i)!$ hoán vị đứng trước hoán vị đã cho. Giải mã làm ngược lại với hạng tính từ 0: thương cho $(n - i)!$ là chỉ số của số cần đặt trong các số chưa dùng, phần dư đi tiếp cho các vị trí sau.

Bước 1: đọc hoán vị không biết trước độ dài. Đề không cho $n$ riêng: độ dài là số số trên dòng đầu, nên đọc cả dòng bằng getline rồi tách số.

string line;
getline(cin, line);
stringstream ss(line);
ll x;
while (ss >> x) a[++n] = x;

Bước 2: xếp hạng. f[i] $= i!$, tới $12! \approx 4{,}8 \cdot 10^8$. c đếm số chưa dùng nhỏ hơn a[i].

ll rk = 1;
for (ll i = 1; i <= n; i++) {
    ll c = 0;
    for (ll v = 1; v < a[i]; v++) c += !used[v];
    rk += c * f[n - i];
    used[a[i]] = 1;
}

Bước 3: giải mã. Làm việc với $p - 1$. c-- == 0 tìm số chưa dùng thứ c (đếm từ 0).

p--;
for (ll i = 1; i <= n; i++) {
    ll c = p / f[n - i];
    p %= f[n - i];
    for (ll v = 1; v <= n; v++)
        if (!used[v] && c-- == 0) {
            used[v] = 1;
            cout << v << ' ';
            break;
        }
}

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

ll n, a[15], f[15], used[15];

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

    string line;
    getline(cin, line);
    stringstream ss(line);
    ll x;
    while (ss >> x) a[++n] = x;
    ll p;
    cin >> p;
    f[0] = 1;
    for (ll i = 1; i <= n; i++) f[i] = f[i - 1] * i;
    ll rk = 1;
    for (ll i = 1; i <= n; i++) {
        ll c = 0;
        for (ll v = 1; v < a[i]; v++) c += !used[v];
        rk += c * f[n - i];
        used[a[i]] = 1;
    }
    cout << rk << '\n';
    for (ll v = 1; v <= n; v++) used[v] = 0;
    p--;
    for (ll i = 1; i <= n; i++) {
        ll c = p / f[n - i];
        p %= f[n - i];
        for (ll v = 1; v <= n; v++)
            if (!used[v] && c-- == 0) {
                used[v] = 1;
                cout << v << ' ';
                break;
            }
    }
    cout << '\n';
}

ChạyInput3 1 2
6

Output5
3 2 1

Độ phức tạp: $O(n^2)$.

Với $n$ lớn, bước chậm là đếm số số chưa dùng nhỏ hơn $a_i$. Đó là câu hỏi tổng tiền tố trên mảng 0/1 có sửa, nên Fenwick (bài 16) trả lời trong $O(\log n)$:

Fenwick nhanh hơn vòng lặp cỡ hai trăm lần ở $n = 30000$, đưa cả bài về $O(n \log n)$. Với $n \le 12$ như bài trên thì vòng lặp là đủ.

Đếm đuôi

Khi ràng buộc phức tạp hơn “dùng mỗi thứ một số lần”, số cách hoàn thiện không còn công thức gọn. Nhưng nó thường chỉ phụ thuộc vào vị trí và một ít trạng thái của tiền tố: chiều cao hiện tại của đường đi, số ngoặc đang mở, số bit 0 liên tiếp ở cuối.

Quy hoạch động $ways[i][h]$ là số cách đi từ vị trí $i$ với trạng thái $h$ tới hết, tính từ cuối về đầu. Giải mã và xếp hạng giữ nguyên khuôn, chỉ thay $cnt(c)$ bằng $ways[i + 1][h']$ với $h'$ là trạng thái sau khi đặt $c$.

Khi điều kiện lại nói về cả đối tượng, như “độ sâu lớn nhất đúng bằng $k$”, thêm vào trạng thái phần tiền tố đã đạt (độ sâu lớn nhất tới giờ), hoặc đếm bằng hiệu: số đối tượng có độ sâu không quá $k$ trừ số có độ sâu không quá $k - 1$.

Ví dụDãy Catalan Xếp Hạng Và Truy Ngược

Đề. Dãy Catalan cấp $n \le 15$ dài $2n + 1$, đầu và cuối bằng 0, các số không âm, hai số kề hơn kém đúng 1. In thứ hạng của một dãy cho trước và dãy ở thứ hạng $k$.

Lời giải. Khuôn chung của xếp hạng theo thứ tự từ điển: đếm số cách hoàn thành dãy từ mỗi trạng thái, rồi đi dọc dãy, mỗi lần dãy chọn một nhánh lớn hơn thì cộng số dãy của các nhánh nhỏ hơn. Ở đây từ giá trị $h$ chỉ đi tới $h - 1$ (nhỏ hơn, đứng trước) hoặc $h + 1$.

Bước 1: số cách hoàn thành. ways[i][h] là số cách điền từ vị trí $i$ đang có giá trị $h$ tới cuối; chỉ có đúng một cách kết thúc là ways[L][0] = 1. Mọi giá trị dưới số Catalan $C_{15} \approx 9{,}7 \cdot 10^6$.

ways[L][0] = 1;
for (ll i = L - 1; i >= 1; i--)
    for (ll h = 0; h <= n; h++) ways[i][h] = (h ? ways[i + 1][h - 1] : 0) + ways[i + 1][h + 1];

Bước 2: xếp hạng. Ở mỗi vị trí dãy đi lên trong khi đi xuống cũng hợp lệ (giá trị hiện tại dương), mọi dãy đi xuống tại đó đứng trước; cộng số cách của chúng.

ll rk = 1;
for (ll i = 1; i < L; i++)
    if (c[i + 1] == c[i] + 1 && c[i] > 0) rk += ways[i + 1][c[i] - 1];

Bước 3: giải mã. Thử đi xuống trước vì giá trị nhỏ hơn đứng trước. $k$ không quá số cách đi xuống thì đi xuống, ngược lại trừ đi và đi lên.

for (ll i = 1; i < L; i++) {
    ll down = h ? ways[i + 1][h - 1] : 0;
    if (k <= down) h--;
    else {
        k -= down;
        h++;
    }
    cout << ' ' << h;
}

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

ll n, L, c[35], ways[35][20];

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

    cin >> n;
    L = 2 * n + 1;
    for (ll i = 1; i <= L; i++) cin >> c[i];
    ll k;
    cin >> k;
    ways[L][0] = 1;
    for (ll i = L - 1; i >= 1; i--)
        for (ll h = 0; h <= n; h++) ways[i][h] = (h ? ways[i + 1][h - 1] : 0) + ways[i + 1][h + 1];
    ll rk = 1;
    for (ll i = 1; i < L; i++)
        if (c[i + 1] == c[i] + 1 && c[i] > 0) rk += ways[i + 1][c[i] - 1];
    cout << rk << '\n';
    ll h = 0;
    cout << 0;
    for (ll i = 1; i < L; i++) {
        ll down = h ? ways[i + 1][h - 1] : 0;
        if (k <= down) h--;
        else {
            k -= down;
            h++;
        }
        cout << ' ' << h;
    }
    cout << '\n';
}

ChạyInput3
0 1 2 1 2 1 0
3

Output4
0 1 2 1 0 1 0

Độ phức tạp: $O(n^2)$ cho bảng, $O(n)$ cho mỗi lượt đi.

Ví dụDãy ngoặc cấp k

Đề. Các dãy ngoặc đúng độ dài $N \le 60$ có độ sâu lớn nhất đúng bằng $k$, sắp theo từ điển với ( đứng trước ). In số dãy như vậy và thứ hạng của một dãy cho trước.

Lời giải. “Độ sâu lớn nhất đúng bằng $k$” khó đếm thẳng, nhưng “không vượt $L$” thì dễ: số dãy độ sâu đúng $k$ là số dãy không vượt $k$ trừ số dãy không vượt $k - 1$. Xếp hạng theo khuôn từ điển: ở vị trí dãy đặt ), mọi dãy đặt ( tại đó đứng trước.

Bước 1: bảng “không vượt $L$”. dp[L][r][b] là số cách viết $r$ ký tự còn lại từ số ngoặc mở $b$, về 0 mà không lúc nào vượt $L$. Mỗi bước mở thêm (nếu chưa vượt $L$) hoặc đóng (nếu còn ngoặc mở).

for (ll L = 0; L <= k; L++) {
    dp[L][0][0] = 1;
    for (ll r = 1; r <= n; r++)
        for (ll b = 0; b <= L; b++) dp[L][r][b] = (b + 1 <= L ? dp[L][r - 1][b + 1] : 0) + (b ? dp[L][r - 1][b - 1] : 0);
}
cout << dp[k][n][0] - dp[k - 1][n][0] << '\n';

Bước 2: xếp hạng. bal, mx theo dõi số mở và độ sâu lớn nhất của tiền tố thật. Ở vị trí dãy đặt ), thử đặt ( thay vào: số mở thành nb, độ sâu tiền tố thành nm. Nếu nm > k thì không có dãy nào; nếu tiền tố đã chạm $k$ thì đuôi chỉ cần không vượt $k$; nếu chưa chạm thì đuôi phải chạm đúng $k$, đếm bằng hiệu hai bảng.

for (ll i = 0; i < n; i++) {
    if (s[i] == ')') {
        ll nb = bal + 1, nm = max(mx, nb), r = n - i - 1;
        if (nm == k) rk += dp[k][r][nb];
        else if (nm < k) rk += dp[k][r][nb] - dp[k - 1][r][nb];
    }
    bal += (s[i] == '(' ? 1 : -1);
    mx = max(mx, bal);
}

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

ll n, k, dp[32][62][32];
string s;

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

    cin >> n >> k >> s;
    for (ll L = 0; L <= k; L++) {
        dp[L][0][0] = 1;
        for (ll r = 1; r <= n; r++)
            for (ll b = 0; b <= L; b++) dp[L][r][b] = (b + 1 <= L ? dp[L][r - 1][b + 1] : 0) + (b ? dp[L][r - 1][b - 1] : 0);
    }
    cout << dp[k][n][0] - dp[k - 1][n][0] << '\n';
    ll rk = 1, bal = 0, mx = 0;
    for (ll i = 0; i < n; i++) {
        if (s[i] == ')') {
            ll nb = bal + 1, nm = max(mx, nb), r = n - i - 1;
            if (nm == k) rk += dp[k][r][nb];
            else if (nm < k) rk += dp[k][r][nb] - dp[k - 1][r][nb];
        }
        bal += (s[i] == '(' ? 1 : -1);
        mx = max(mx, bal);
    }
    cout << rk << '\n';
}

ChạyInput6 2
(()())

Output3
1

Độ phức tạp: $O(k \cdot N \cdot k)$ cho bảng, $O(N)$ cho xếp hạng.

Số đếm rất lớn

Thứ $K$ tới $10^{18}$ mà số đối tượng có thể còn lớn hơn: số cách hoàn thiện tràn ll. Chỉ cần biết số cách có lớn hơn $K$ hay không, nên chặn trần: mọi phép cộng và nhân dừng ở một ngưỡng như $2 \cdot 10^{18}$. Khối có kích thước bị chặn vẫn được so sánh đúng với $K$.

Cũng hay gặp: số đối tượng tăng như dãy Fibonacci hay lũy thừa của 2, nên chỉ vài chục vị trí đầu cần đếm thật, còn lại số cách đã vượt mọi $K$. Chẳng hạn chia $1..n$ thành các khối liên tiếp dài 1 hoặc 2 (khối dài 2 bị đảo) có Fibonacci cách; ở vị trí $i$, khối dài 1 mở $f_{n-i}$ hoán vị, và chọn khối dài 1 hay 2 theo $K$ so với số đó.

Từ cuối về đầu

Khi đề hỏi đối tượng nhỏ nhất theo từ điển trong một tập phức tạp, quy hoạch động có thể lưu thẳng chuỗi tốt nhất làm giá trị. Nhưng hướng duyệt quan trọng: so sánh từ điển do ký tự đầu quyết định, nên tiền tố tốt nhất chưa chắc mở rộng thành chuỗi tốt nhất, còn hậu tố tốt nhất thì luôn đúng khi nối thêm ở phía trước. Vì vậy quy hoạch động từ cuối về đầu: $dp[i][\dots]$ là chuỗi nhỏ nhất dựng từ phần $i..n$, rồi $dp[i] = \min(\text{bỏ } i, \ s_i + dp[i+1][\dots])$.

Ví dụThẻ Chuỗi

Đề. $N \le 50$ thẻ ghi chuỗi chữ thường dài tới 50. Chọn đúng $K$ thẻ và nối theo thứ tự tùy ý để được chuỗi nhỏ nhất theo từ điển.

Lời giải. Hai ý. Thứ nhất, với một tập thẻ đã chọn, nối theo thứ tự sắp bằng phép so sánh $x + y < y + x$ là tốt nhất: đổi hai thẻ kề nhau sai thứ tự không bao giờ làm chuỗi lớn hơn (bài 03). Thứ hai, sau khi sắp mọi thẻ theo thứ tự đó, chọn tập bằng quy hoạch động từ cuối về đầu: $dp[i][j]$ là chuỗi nhỏ nhất dùng đúng $j$ thẻ trong các thẻ $i..N$. Từ đầu về cuối thì sai: tiền tố nhỏ nhất có thể dẫn tới chuỗi lớn hơn, còn hậu tố nhỏ nhất thêm một thẻ vào đầu vẫn là ứng viên tốt nhất.

Bước 1: sắp thẻ. Phép so sánh $a + b < b + a$ bắc cầu, nên sort dùng được.

bool cmp(string a, string b) {
    return a + b < b + a;
}

Bước 2: chọn từ cuối về. ok[i][j] cho biết có cách chọn đúng $j$ thẻ không. Chuyển trạng thái: bỏ thẻ $i$, hoặc lấy thẻ $i$ đứng đầu rồi nối với chuỗi tốt nhất của phần sau. Thẻ $i$ đứng trước mọi thẻ sau nó theo thứ tự đã sắp, nên đặt nó ở đầu là đúng thứ tự nối.

for (ll i = n; i >= 1; i--) {
    ok[i][0] = 1;
    for (ll j = 1; j <= n - i + 1; j++) {
        if (ok[i + 1][j]) {
            dp[i][j] = dp[i + 1][j];
            ok[i][j] = 1;
        }
        if (ok[i + 1][j - 1]) {
            string t = s[i] + dp[i + 1][j - 1];
            if (!ok[i][j] || t < dp[i][j]) dp[i][j] = t;
            ok[i][j] = 1;
        }
    }
}

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

ll n, k;
string s[55], dp[55][55];
bool ok[55][55];

bool cmp(string a, string b) {
    return a + b < b + a;
}

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

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1, cmp);
    ok[n + 1][0] = 1;
    for (ll i = n; i >= 1; i--) {
        ok[i][0] = 1;
        for (ll j = 1; j <= n - i + 1; j++) {
            if (ok[i + 1][j]) {
                dp[i][j] = dp[i + 1][j];
                ok[i][j] = 1;
            }
            if (ok[i + 1][j - 1]) {
                string t = s[i] + dp[i + 1][j - 1];
                if (!ok[i][j] || t < dp[i][j]) dp[i][j] = t;
                ok[i][j] = 1;
            }
        }
    }
    cout << dp[1][k] << '\n';
}

ChạyInput4 3
b
a
baa
ba

Outputabaab

Độ phức tạp: mỗi ô là một chuỗi dài tới $50 \cdot 50$ ký tự, so sánh và nối tốn $O(2500)$: tổng khoảng $50 \cdot 50 \cdot 2500$ phép.