Wiki › Thuật toán › Toán học › Hạng của hoán vị và dãy thứ k

Hạng của hoán vị và dãy thứ k

huunguyen Updated Tháng 9. 29, 2026 Đọc 25 phút 3 lượt xem

Liệt kê mọi hoán vị của $1, 2, \dots, n$ theo thứ tự từ điển, hỏi hoán vị $p$ đứng thứ mấy (hạng của $p$ ), hoặc ngược lại, hoán vị đứng thứ $k$ là gì. Liệt kê thẳng tốn $O (n! \cdot n)$ và bất khả thi ngay khi $n = 13$ . Trang này chỉ cách trả lời cả hai câu hỏi trong $O (n \log n)$ bằng công thức $\sum c_{i} \cdot (n - i)!$ và cây Fenwick, mở rộng sang dãy có phần tử lặp, rồi tổng quát thành kỹ thuật "dựng đáp án thứ $k$ từng vị trí bằng cách đếm số cách hoàn thành" dùng cho xâu, dãy thỏa ràng buộc, đường đi và bài quy hoạch động chữ số. Cuối trang là thuật toán hoán vị kế tiếp (next_permutation).

Thứ tự từ điển

Dãy $a$ đứng trước dãy $b$ (cùng độ dài) theo thứ tự từ điển nếu ở vị trí đầu tiên hai dãy khác nhau, phần tử của $a$ nhỏ hơn. Ví dụ các hoán vị của ${1, 2, 3}$ :

hạng:   1      2      3      4      5      6
      1 2 3  1 3 2  2 1 3  2 3 1  3 1 2  3 2 1

Điểm mấu chốt: thứ tự từ điển so sánh từ trái sang phải, nên vị trí đầu tiên có "trọng số" lớn nhất, giống chữ số hàng cao nhất của một số. Mọi kỹ thuật trên trang này đều khai thác đúng tính chất đó.

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

Đếm các khối hoán vị đứng trước

Hạng của $p$ bằng $1 +$ (số hoán vị nhỏ hơn $p$ ). Một hoán vị $q < p$ khi và chỉ khi có một vị trí $i$ sao cho $q$ trùng $p$ ở $i - 1$ vị trí đầu và $q_{i} < p_{i}$ . Các hoán vị như vậy chia thành khối theo $(i, q_{i})$ :

Cố định tiền tố $p_{1}, \dots, p_{i - 1}$ , tại vị trí $i$ chọn một giá trị $v < p_{i}$ chưa dùng trong tiền tố.
Phần còn lại ( $n - i$ vị trí) xếp tùy ý các giá trị chưa dùng: $(n - i)!$ cách.

Gọi $c_{i}$ là số giá trị chưa dùng nhỏ hơn $p_{i}$ (tức số $j > i$ có $p_{j} < p_{i}$ ). Mỗi lựa chọn $v$ cho đúng một khối kích thước $(n - i)!$ , các khối rời nhau (khác nhau ở vị trí khác nhau đầu tiên), nên

$rank (p) = 1 + \sum_{i = 1}^{n} c_{i} \cdot (n - i)!$

Dãy $(c_{1}, c_{2}, \dots, c_{n})$ gọi là mã Lehmer của $p$ . Vì $0 \leq c_{i} \leq n - i$ , đây chính là biểu diễn của $rank (p) - 1$ trong hệ cơ số giai thừa (factorial number system): chữ số ở "hàng" $(n - i)!$ nằm trong $[0, n - i]$ . Mỗi số trong $[0, n! - 1]$ có đúng một biểu diễn như thế, do đó phép đổi hạng và hoán vị là song ánh. (Tiện thể: $\sum c_{i}$ chính là số nghịch thế của $p$ .)

Ngược lại: hoán vị thứ $k$

Đặt $r = k - 1$ . Chữ số đầu $c_{1} = ⌊ r / (n - 1)! ⌋$ cho biết $p_{1}$ nằm ở khối thứ mấy: $p_{1}$ là giá trị nhỏ thứ $c_{1} + 1$ trong các giá trị chưa dùng. Lấy $r mod (n - 1)!$ rồi lặp lại cho vị trí 2 với $(n - 2)!$ , và cứ thế. Đây là phép đổi $r$ sang cơ số giai thừa, rồi dịch mỗi chữ số thành một giá trị cụ thể.

Vì sao cần Fenwick

Cả hai chiều đều cần một tập "giá trị chưa dùng" hỗ trợ:

Đếm số phần tử nhỏ hơn $x$ (tính $c_{i}$ ),
Tìm phần tử nhỏ thứ $t$ (dựng hoán vị thứ $k$ ),
Xóa một phần tử.

Làm bằng mảng đánh dấu thì mỗi thao tác $O (n)$ , tổng $O (n^{2})$ . Dùng cây Fenwick trên mảng $0 / 1$ (ô $v$ bằng $1$ nếu $v$ chưa dùng): đếm là một truy vấn tổng tiền tố, xóa là cộng $- 1$ , còn tìm phần tử thứ $t$ là hạ nhị phân (binary descent) trên cây, đều $O (\log n)$ .

Ví dụ chạy tay

Hạng của $p = (3, 1, 4, 2)$

 i   p_i   chưa dùng (trước bước i)   c_i = #chưa dùng < p_i   (n-i)!   c_i*(n-i)!
 1    3      {1, 2, 3, 4}                 2   (1, 2)              3! = 6     12
 2    1      {1, 2, 4}                    0                       2! = 2      0
 3    4      {2, 4}                       1   (2)                 1! = 1      1
 4    2      {2}                          0                       0! = 1      0
                                                                   tổng  =    13
 rank = 13 + 1 = 14

Kiểm tra bằng cách nhìn các khối: 6 hoán vị bắt đầu bằng 1, 6 hoán vị bắt đầu bằng 2 (đã là 12 hoán vị đứng trước). Trong khối bắt đầu bằng 3, các hoán vị bắt đầu bằng 3 1 là 3 1 2 4 (hạng 13) rồi 3 1 4 2 (hạng 14). Khớp.

        đầu = 1          đầu = 2              đầu = 3                 đầu = 4
   [ 6 hoán vị ]    [ 6 hoán vị ]    [3 1 ..][3 2 ..][3 4 ..]     [ 6 hoán vị ]
   hạng 1..6        hạng 7..12        13,14   15,16   17,18        hạng 19..24
                                         ^
                                     3 1 4 2 là hạng 14

Hoán vị thứ $k = 14$ với $n = 4$

$r = 13$ . Đổi sang cơ số giai thừa và chọn phần tử nhỏ thứ $(c_{i} + 1)$ :

 bước   r    (n-i)!   c_i = r / (n-i)!   r mới = r % (n-i)!   chưa dùng     chọn
  1    13      6           2                  1               {1,2,3,4}   thứ 3 -> 3
  2     1      2           0                  1               {1,2,4}     thứ 1 -> 1
  3     1      1           1                  0               {2,4}       thứ 2 -> 4
  4     0      1           0                  0               {2}         thứ 1 -> 2
 kết quả: (3, 1, 4, 2)

Đúng là phép ngược của bảng trước: mã Lehmer $(2, 0, 1, 0)$ xuất hiện ở cả hai.

Cài đặt

Hạng và hoán vị thứ $k$ bằng Fenwick ( $n \leq 20$ , giá trị chính xác)

$20! \approx 2, 43 \cdot 10^{18}$ vẫn vừa unsigned long long (thậm chí vừa long long), nên với $n \leq 20$ ta tính được hạng chính xác.

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

// Fenwick tree over values 1..n
struct Fenwick {
    int n, LOG;
    vector<int> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {
        LOG = 1;
        while ((1 << LOG) <= n) LOG++;
    }
    void add(int i, int d) { for (; i <= n; i += i & -i) t[i] += d; }
    int sum(int i) const { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    // smallest index p with sum(p) >= k (k >= 1), binary descent in O(log n)
    int kth(int k) const {
        int pos = 0;
        for (int b = LOG; b >= 0; b--) {
            int nxt = pos + (1 << b);
            if (nxt <= n && t[nxt] < k) { pos = nxt; k -= t[nxt]; }
        }
        return pos + 1;
    }
};

// Rank (1-based) of a permutation of 1..n, n <= 20
ull permRank(const vector<int>& p) {
    int n = p.size();
    vector<ull> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    Fenwick fw(n);
    for (int v = 1; v <= n; v++) fw.add(v, 1);      // all values unused
    ull rank = 0;
    for (int i = 0; i < n; i++) {
        int c = fw.sum(p[i] - 1);                   // unused values smaller than p[i]
        rank += (ull)c * fact[n - 1 - i];
        fw.add(p[i], -1);                           // mark p[i] as used
    }
    return rank + 1;
}

// k-th permutation (1-based k) of 1..n, n <= 20
vector<int> kthPerm(int n, ull k) {
    vector<ull> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    Fenwick fw(n);
    for (int v = 1; v <= n; v++) fw.add(v, 1);
    k--;                                            // switch to 0-based
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        ull block = fact[n - 1 - i];
        int c = k / block;                          // factorial-base digit
        k %= block;
        p[i] = fw.kth(c + 1);                       // (c+1)-th smallest unused value
        fw.add(p[i], -1);
    }
    return p;
}

int main() {
    printf("%llu\n", permRank({3, 1, 4, 2}));         // 14
    for (int x : kthPerm(4, 14)) printf("%d ", x);    // 3 1 4 2
    puts("");
}

Hàm kth của Fenwick: đi từ bit cao xuống bit thấp, mỗi bước thử "nhảy" thêm $2^{b}$ ô; nếu tổng của khối đó vẫn nhỏ hơn $k$ thì nhảy và trừ $k$ đi, ngược lại giữ nguyên. Cuối cùng pos là chỉ số lớn nhất có tổng tiền tố $< k$ , nên đáp án là pos + 1. Toàn bộ chỉ $O (\log n)$ , không cần tìm kiếm nhị phân lồng truy vấn ( $O (\log^{2} n)$ ).

Hạng theo modulo khi $n$ lớn

Khi $n$ tới $10^{5}$ hay $10^{6}$ , hạng có hàng trăm nghìn chữ số, đề thường yêu cầu lấy theo modulo $M$ . Công thức không đổi, chỉ cần giai thừa theo modulo. Khối dưới đây không tự chạy riêng được: nó dùng lại struct Fenwick của khối đầu, nên hãy chép nó vào sau struct Fenwick (trước main) trong chương trình ở trên.

const long long MOD = 1e9 + 7;

// Rank (1-based) mod MOD, O(n log n); reuses struct Fenwick above
long long permRankMod(const vector<int>& p) {
    int n = p.size();
    vector<long long> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    Fenwick fw(n);
    for (int v = 1; v <= n; v++) fw.add(v, 1);
    long long rank = 0;
    for (int i = 0; i < n; i++) {
        long long c = fw.sum(p[i] - 1);
        rank = (rank + c * fact[n - 1 - i]) % MOD;
        fw.add(p[i], -1);
    }
    return (rank + 1) % MOD;
}

Chiều ngược lại (hoán vị thứ $k$ ) với $n$ lớn thì $k$ thường chỉ tới $10^{18}$ , xem mục ⚠️ bên dưới: chỉ khoảng $20$ phần tử cuối thực sự bị xáo.

Python (dễ đọc, $O (n^{2})$ , dùng số nguyên lớn sẵn có)

from math import factorial


def perm_rank(p):
    """1-based lexicographic rank of permutation p of 1..n."""
    n = len(p)
    rank = 0
    for i in range(n):
        # unused values smaller than p[i] = later elements smaller than p[i]
        c = sum(1 for j in range(i + 1, n) if p[j] < p[i])
        rank += c * factorial(n - 1 - i)
    return rank + 1


def kth_perm(n, k):
    """k-th (1-based) permutation of 1..n in lexicographic order."""
    unused = list(range(1, n + 1))
    k -= 1
    res = []
    for i in range(n):
        digit, k = divmod(k, factorial(n - 1 - i))
        res.append(unused.pop(digit))
    return res


print(perm_rank([3, 1, 4, 2]), kth_perm(4, 14))  # 14 [3, 1, 4, 2]

Hạng của dãy có phần tử lặp (hoán vị đa tập)

Bài toán: xâu $s$ độ dài $n$ (có thể lặp chữ cái), hỏi $s$ đứng thứ mấy trong danh sách các cách sắp xếp khác nhau của các chữ cái của nó. Số cách sắp xếp của đa tập có ${cnt}_{a}$ chữ $a$ , ${cnt}_{b}$ chữ $b$ , ... là hệ số đa thức

$\frac{m!}{\prod_{x} {cnt}_{x}!}, m = \sum_{x} {cnt}_{x} .$

Lập luận khối vẫn y hệt: tại vị trí $i$ (còn $m = n - i + 1$ chữ chưa đặt), với mỗi loại chữ $x < s_{i}$ còn trong kho, số xâu bắt đầu bằng $x$ là

$\frac{(m - 1)!}{\prod_{y} {cnt}_{y}!} \cdot {cnt}_{x} .$

(Đặt $x$ làm giảm ${cnt}_{x}$ đi một, tức nhân thêm ${cnt}_{x}$ vào tử.) Cộng theo mọi $x < s_{i}$ :

$rank (s) = 1 + \sum_{i = 1}^{n} \frac{(m_{i} - 1)!}{\prod_{y} {cnt}_{y}!} \cdot (\sum_{x < s_{i}} {cnt}_{x}) .$

Điểm khác với hoán vị thường: đếm theo loại chữ chứ không theo từng phần tử, nếu không một xâu sẽ bị đếm nhiều lần (hai chữ a đổi chỗ vẫn là cùng một xâu).

Ví dụ $s =$ baba (2 chữ a, 2 chữ b, tổng $\frac{4!}{2! 2!} = 6$ xâu: aabb abab abba baab baba bbaa):

 i  s_i  kho (a,b)  m   sum cnt_x (x < s_i)   (m-1)!/prod cnt!     đóng góp
 1   b    (2,2)     4        2 (chữ a)         3!/(2!2!) = 1.5       3
 2   a    (2,1)     3        0                 -                     0
 3   b    (1,1)     2        1 (chữ a)         1!/(1!1!) = 1         1
 4   a    (1,0)     1        0                 -                     0
 rank = 3 + 1 + 1 = 5     (baba đứng thứ 5 trong danh sách trên)

Giá trị trung gian $1, 5$ không nguyên nhưng tích với $\sum {cnt}_{x}$ luôn nguyên; khi tính theo modulo nguyên tố thì dùng nghịch đảo modulo nên không gặp vấn đề (xem Tổ hợp).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

ll power(ll a, ll e) {
    ll r = 1; a %= MOD;
    for (; e > 0; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD;
    return r;
}

// Rank (1-based, mod MOD) of s among all distinct rearrangements of its letters
ll multisetRank(const string& s) {
    int n = s.size();
    vector<ll> fact(n + 1, 1), inv(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    inv[n] = power(fact[n], MOD - 2);
    for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;

    array<int, 26> cnt{};
    for (char ch : s) cnt[ch - 'a']++;
    ll invProd = 1;                          // 1 / prod(cnt[c]!)
    for (int c = 0; c < 26; c++) invProd = invProd * inv[cnt[c]] % MOD;

    ll rank = 0;
    for (int i = 0; i < n; i++) {
        int m = n - i;                       // letters still unplaced
        int cur = s[i] - 'a';
        ll smaller = 0;                      // letters in stock that are < s[i]
        for (int c = 0; c < cur; c++) smaller += cnt[c];
        rank = (rank + fact[m - 1] * invProd % MOD * (smaller % MOD)) % MOD;
        // place s[i]: cnt[cur]! becomes (cnt[cur]-1)!, so multiply invProd by cnt[cur]
        invProd = invProd * cnt[cur] % MOD;
        cnt[cur]--;
    }
    return (rank + 1) % MOD;
}

int main() {
    cout << multisetRank("baba") << "\n";    // 5
    cout << multisetRank("banana") << "\n";  // 35
}

Với bảng chữ cái nhỏ (26), vòng for c < cur là $O (26)$ mỗi bước. Nếu "chữ cái" là số nguyên tới $10^{5}$ thì thay vòng đó bằng Fenwick trên mảng $cnt$ , đưa tổng về $O (n \log n)$ .

Kỹ thuật tổng quát: dựng đáp án thứ $k$ bằng đếm số cách hoàn thành

Hai thuật toán trên là trường hợp riêng của một khuôn rất hay gặp. Cho tập đối tượng là các dãy độ dài $n$ thỏa một ràng buộc, sắp theo thứ tự từ điển, cần tìm đối tượng thứ $k$ :

Mô tả trạng thái sau khi đã chọn một tiền tố, sao cho số cách hoàn thành chỉ phụ thuộc vào trạng thái (không phụ thuộc toàn bộ tiền tố).
Đếm $f (trạng thái, số vị trí còn lại)$ = số cách hoàn thành hợp lệ, thường bằng quy hoạch động hoặc công thức tổ hợp.
Dựng: tại mỗi vị trí, thử các lựa chọn theo thứ tự tăng dần. Lựa chọn $x$ dẫn tới trạng thái có $w$ cách hoàn thành. Nếu $k \leq w$ thì chọn $x$ và sang vị trí sau; ngược lại $k - = w$ (bỏ qua cả khối) và thử lựa chọn tiếp theo.

Chiều ngược lại (hạng của một đối tượng) là cộng dồn các $w$ bị bỏ qua. Với hoán vị, trạng thái là "tập giá trị chưa dùng" và $w = (n - i)!$ không phụ thuộc lựa chọn, nên chỉ cần phép chia thay cho vòng thử.

Ví dụ: xâu nhị phân thứ $k$ không có hai số 1 kề nhau

Trạng thái: ký tự vừa đặt (last). $f [len] [last]$ = số cách điền $len$ ký tự nữa:

$f [0] [\cdot] = 1, f [len] [0] = f [len - 1] [0] + f [len - 1] [1], f [len] [1] = f [len - 1] [0] .$

Với $n = 5$ (có 13 xâu hợp lệ), tìm xâu thứ $k = 7$ :

len	0	1	2	3	4
$f [len] [0]$	1	2	3	5	8
$f [len] [1]$	1	1	2	3	5

 vị trí  còn lại  last   thử '0': w          thử '1': w          k      chọn
   1        4      0     f[4][0]=8, 7<=8      -                  7      '0'
   2        3      0     f[3][0]=5, 7>5       f[3][1]=3, 2<=3    7->2   '1'
   3        2      1     f[2][0]=3, 2<=3      (cấm '1')          2      '0'
   4        1      0     f[1][0]=2, 2<=2      -                  2      '0'
   5        0      0     f[0][0]=1, 2>1       f[0][1]=1, 1<=1    2->1   '1'
 kết quả: 01001

Liệt kê tay 00000 00001 00010 00100 00101 01000 01001 ... thấy 01001 đúng là xâu thứ 7.

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

// k-th (1-based) binary string of length n with no two adjacent '1', or "-1"
string kthNoAdjacentOnes(int n, ll k) {
    const ll CAP = 2e18;                     // saturate counts to avoid overflow
    vector<array<ll, 2>> f(n + 1);
    f[0] = {1, 1};
    for (int len = 1; len <= n; len++) {
        f[len][0] = min(CAP, f[len - 1][0] + f[len - 1][1]);
        f[len][1] = f[len - 1][0];
    }
    if (k > f[n][0]) return "-1";            // fewer than k valid strings
    string res;
    int last = 0;
    for (int pos = 0; pos < n; pos++) {
        int rem = n - pos - 1;               // characters after this one
        for (int ch = 0; ch <= 1; ch++) {    // try choices in increasing order
            if (ch == 1 && last == 1) continue;
            ll ways = f[rem][ch];
            if (k <= ways) { res += char('0' + ch); last = ch; break; }
            k -= ways;                       // skip the whole block
        }
    }
    return res;
}

int main() {
    cout << kthNoAdjacentOnes(5, 7) << "\n";                        // 01001
    cout << kthNoAdjacentOnes(100, 1000000000000000000LL) << "\n";  // works despite huge counts
}

Cùng khuôn này áp dụng cho:

Số thứ $k$ thỏa tính chất chữ số: trạng thái là trạng thái của DP chữ số (tổng chữ số, số dư, số chữ số đặc biệt, ...), thử chữ số $0 . .9$ theo thứ tự.
Xâu/dãy thứ $k$ với số lượng mỗi loại cho trước: $w$ là hệ số đa thức như mục trước.
Đường đi thứ $k$ theo thứ tự từ điển trên DAG: $w$ = số đường từ đỉnh kế tiếp tới đích (DP trên đồ thị), thử các đỉnh kề theo chỉ số tăng.

Hoán vị kế tiếp (next_permutation)

Khi cần duyệt tuần tự các hoán vị (thay vì nhảy tới hạng bất kỳ), dùng thuật toán sinh hoán vị kế tiếp:

Tìm $i$ lớn nhất có $a_{i} < a_{i + 1}$ . Nếu không có, $a$ đang là hoán vị cuối (giảm dần).
Tìm $j$ lớn nhất có $a_{j} > a_{i}$ (phần đuôi $a_{i + 1 . . n}$ đang giảm dần nên đây là phần tử nhỏ nhất lớn hơn $a_{i}$ trong đuôi).
Đổi chỗ $a_{i}$ và $a_{j}$ .
Đảo ngược đuôi $a_{i + 1 . . n}$ (nó vẫn giảm dần sau bước 3, đảo lại thành tăng dần: nhỏ nhất có thể).

Vì sao đúng: đuôi giảm dần là hoán vị lớn nhất của tập giá trị đó, nên không thể tăng hoán vị mà chỉ thay đuôi; phải tăng $a_{i}$ lên ít nhất có thể rồi làm đuôi nhỏ nhất có thể.

 a = 1 3 5 4 2
       ^ ~~~~~    i = 2 (a_2 = 3 < a_3 = 5), đuôi 5 4 2 giảm dần
 j = 4 (a_4 = 4 là số cuối cùng > 3)
 đổi:   1 4 5 3 2
 đảo đuôi: 1 4 2 3 5

Khối dưới đây chỉ là một hàm rời (không có #include và main): chép nó vào một chương trình đã có #include <bits/stdc++.h> và using namespace std;, ví dụ chương trình Fenwick ở đầu trang.

// Manual next_permutation, returns false if a is already the last permutation
bool nextPerm(vector<int>& a) {
    int n = a.size(), i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;  // longest non-increasing suffix
    if (i < 0) return false;
    int j = n - 1;
    while (a[j] <= a[i]) j--;                // rightmost element greater than a[i]
    swap(a[i], a[j]);
    reverse(a.begin() + i + 1, a.end());     // suffix becomes increasing
    return true;
}

Trong C++ có sẵn std::next_permutation(a.begin(), a.end()) (và prev_permutation), hoạt động đúng cả với dãy có phần tử lặp (sinh các cách sắp xếp khác nhau, không lặp). Khác biệt nhỏ: khi đã là hoán vị cuối, bản std trả false và đưa dãy về hoán vị đầu (tăng dần), còn hàm tự viết ở trên giữ nguyên.

Một bước có thể tốn $O (n)$ , nhưng trung bình chỉ $O (1)$ : đuôi có độ dài $m$ chỉ bị thay đổi khoảng một lần trong $m!$ bước, nên duyệt $k$ hoán vị liên tiếp tốn $O (n + k)$ tổng cộng (cộng thêm chi phí xử lý mỗi hoán vị).

Độ phức tạp

Thao tác	Thời gian	Bộ nhớ	Lý do
Hạng của hoán vị (Fenwick)	$O (n \log n)$	$O (n)$	$n$ bước, mỗi bước một truy vấn tổng và một cập nhật $O (\log n)$
Hoán vị thứ $k$ (Fenwick)	$O (n \log n)$	$O (n)$	$n$ bước, mỗi bước một phép chia, một lần hạ nhị phân và một cập nhật
Bản mảng đánh dấu / Python `list.pop`	$O (n^{2})$	$O (n)$	mỗi bước quét hoặc xóa trong mảng $O (n)$
Hạng đa tập, bảng chữ $σ$	$O (n σ)$ hoặc $O (n \log σ)$	$O (n + σ)$	tổng $cnt$ các chữ nhỏ hơn, cộng $O (n)$ tiền xử lý giai thừa
Dựng đối tượng thứ $k$ (tổng quát)	$O (DP) + O (n \cdot A)$	kích thước bảng DP	$A$ = số lựa chọn thử tại mỗi vị trí
`next_permutation`	$O (n)$ xấu nhất, $O (1)$ trung bình	$O (1)$	đuôi dài $m$ đổi khoảng một lần mỗi $m!$ bước

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

Lệch 0 và 1. Công thức $\sum c_{i} (n - i)!$ cho số hoán vị đứng trước, tức hạng tính từ $0$ . Đề đánh số từ $1$ thì phải cộng $1$ ; chiều ngược lại phải k-- trước khi đổi cơ số. Quên một trong hai sẽ lệch đúng một hoán vị, rất khó thấy trên ví dụ nhỏ.
Tràn số với giai thừa. $20! < 2^{63}$ nhưng $21! > 2^{64}$ . Tính hạng chính xác chỉ được với $n \leq 20$ ; lớn hơn thì dùng modulo, __int128 (tới $n \leq 33$ ) hoặc số lớn. Trong kỹ thuật "đếm số cách hoàn thành", số cách có thể vượt $10^{18}$ dù $k$ nhỏ: chặn trên (saturate) bằng min(CAP, ...) như code ở trên thay vì để tràn thành số âm.
Tưởng $n$ lớn thì phải xáo cả $n$ phần tử. Với $n = 10^{9}$ và $k \leq 10^{18}$ , vì $20! > 10^{18}$ nên chỉ khoảng 20 phần tử cuối bị xáo, $n - 20$ phần tử đầu giữ nguyên $1, 2, \dots$ . Tìm $m$ nhỏ nhất có $m! \geq k$ , dựng hoán vị thứ $k$ của $m$ giá trị cuối, phần đầu là hoán vị đơn vị. Nhớ kiểm tra trường hợp $n! < k$ (không tồn tại) khi $n$ nhỏ.
Hạng theo modulo không so sánh được. Hạng mod $10^{9} + 7$ chỉ dùng để in ra; không thể lấy nó để suy ngược hoán vị hay so sánh hai hoán vị. Muốn dựng ngược thì $k$ phải được cho chính xác.
Đếm theo phần tử thay vì theo loại trong đa tập. Nếu áp công thức hoán vị thường cho xâu có chữ lặp, một xâu bị đếm nhiều lần (các bản sao chữ giống nhau bị coi là khác nhau), và số lần lặp còn không đều giữa các khối nên không sửa được bằng cách chia kết quả cuối cho một hằng số. Luôn đếm "các loại chữ nhỏ hơn còn trong kho" và chia cho $\prod cnt!$ ngay trong từng khối.
Thứ tự thử lựa chọn sai chiều. Thứ tự từ điển tăng dần thì thử lựa chọn nhỏ trước; nếu đề dùng thứ tự từ điển ngược hoặc thứ tự "xâu ngắn hơn đứng trước" (khi các đối tượng có độ dài khác nhau) thì phải đổi thứ tự thử cho khớp, và cân nhắc đối tượng "dừng ở đây" như một lựa chọn riêng.
Hạ nhị phân Fenwick sai điều kiện. Điều kiện nhảy là t[nxt] < k (chặt). Viết <= thì pos thành chỉ số lớn nhất có tổng tiền tố $\leq k$ , nên hàm trả về phần tử chưa dùng kế tiếp (thứ $k + 1$ ) thay vì phần tử thứ $k$ , kể cả khi không có ô $0$ nào (mọi ô bằng $1$ thì kth(k) trả $k + 1$ ). Ngoài ra LOG phải đủ lớn để $2^{LOG} > n$ .
Dùng next_permutation để nhảy xa. Gọi $k$ lần khi $k$ tới $10^{12}$ là quá chậm; khi chỉ cần hoán vị ở vị trí xa, hãy tính hạng hiện tại, cộng $k$ , rồi dựng lại hoán vị bằng cơ số giai thừa (thường chỉ trên đoạn đuôi ngắn).

Biến thể / Mở rộng

Cộng hai hoán vị theo hạng. Hoán vị có hạng $(rank (p) + rank (q)) mod n!$ tính được mà không cần số lớn: cộng hai mã Lehmer như cộng hai số trong cơ số giai thừa (chữ số hàng $(n - i)!$ nhớ sang khi vượt $n - i$ ), rồi dựng lại bằng Fenwick. Tổng $O (n \log n)$ .
Nhảy $x$ hoán vị liên tiếp nhiều lần. Giữ tổng số bước đã nhảy $K$ : sau $K$ bước kế tiếp tính từ hoán vị đơn vị, ta đang ở hoán vị thứ $K + 1$ (hạng tính từ $0$ bằng $K$ ). Vì $K$ thường nhỏ hơn $20!$ nên chỉ cần dựng lại hoán vị thứ $K + 1$ của khoảng $15$ đến $20$ phần tử cuối sau mỗi lần nhảy.
Tập chưa dùng không phải $1 . . n$ . Nếu giá trị lớn hoặc thưa, nén tọa độ trước; nếu cần chèn/xóa tùy ý trong thứ tự, có thể thay Fenwick bằng segment tree hoặc treap hỗ trợ tìm phần tử thứ $k$ .
Số nghịch thế. $\sum c_{i}$ là số cặp nghịch thế, tính cùng vòng lặp với hạng. Ngược lại, mã Lehmer cho phép dựng hoán vị có đúng một dãy "số phần tử nhỏ hơn phía sau" cho trước.
Đếm thay vì dựng. Khi đề hỏi "có bao nhiêu đối tượng nhỏ hơn $X$ ", đó chính là hạng của $X$ trừ $1$ , tính bằng cách cộng dồn các khối bị bỏ qua; đây là cùng cơ chế với việc đếm số $\leq N$ trong DP chữ số.

Bài tập luyện

Luyện kỹ thuật

Mã Số Bò (cowids) (Trung cấp) số nhị phân thứ $N$ có đúng $K$ bit 1: trước hết xác định độ dài bằng cách đếm $(\binom{L - 1}{K - 1})$ số cho mỗi độ dài $L$ , sau đó dựng từng bit bằng đếm số cách đặt các bit 1 còn lại.
Xâu đẹp thứ K (kthbeaut) (Trung cấp) dạng đơn giản nhất của "đếm số cách hoàn thành": vị trí chữ b thứ nhất quyết định một khối các xâu có kích thước tính được ngay, bỏ qua từng khối cho tới khi chứa $k$ .
Thứ tự hoán vị (permorder) (Trung cấp) cài đặt trực tiếp cả hai chiều: hoán vị thứ $k$ và hạng của hoán vị với $n \leq 20$ (hạng vừa kiểu 64 bit).
Hoán vị may mắn (luckyperm) (Kỳ cựu) $n$ tới $10^{9}$ nhưng $k \leq 10^{9} < 13!$ , nên chỉ khoảng 13 phần tử cuối bị xáo; phần đầu là hoán vị đơn vị, xử lý riêng bằng cách đếm số may mắn.
Hoán vị dài (longperm) (Chuyên gia) tổng số lần "hoán vị kế tiếp" không vượt $2 \cdot 10^{10} < 15!$ , nên giữ tổng số bước và dựng lại hoán vị của đoạn đuôi ngắn bằng cơ số giai thừa thay vì gọi next_permutation từng bước.

Kho bài hiện chưa có bài luyện riêng cho hạng hoán vị với $n$ lớn (Fenwick + modulo) hay hạng của hoán vị đa tập; Đếm hoán vị phân biệt (cntperms) (Nghiệp dư) luyện được bước đếm hệ số đa thức $\frac{n!}{\prod cnt!}$ mà công thức hạng đa tập dùng lại.

Đề VOI

Xâu đối xứng (voi17_qpalin) (Kỳ cựu) VOI 2017: tìm xâu thứ $t$ theo thứ tự từ điển. Hãy tìm một trạng thái nhỏ (chỉ cần tính chẵn lẻ của số lần xuất hiện mỗi chữ và số tiền tố tốt đã gặp) để đếm số cách hoàn thành, và để ý số lượng xâu có thể vượt 64 bit.
Chất lượng dịch vụ (voi14_qos) (Kỳ cựu) VOI 2014: đường truyền thứ $k$ theo thứ tự từ điển. Sau Dijkstra, "độ dư" so với đường ngắn nhất rất nhỏ, nên đếm số đường theo trạng thái (nút, độ dư) rồi dựng đường từng nút một.
Cây hoán vị (voi15_tsort) (Chuyên gia) VOI 2015: duyệt $k$ hoán vị liên tiếp bằng thuật toán hoán vị kế tiếp. Mỗi bước chỉ đổi một đoạn đuôi có độ dài trung bình rất nhỏ, nên hãy lưu trạng thái kiểm tra sau mỗi tiền tố để chỉ tính lại phần đuôi.
Bài tập đêm giáng sinh (voi24_noel) (Chuyên gia) VOI 2024: dựng dãy mã hóa thứ $X$ theo thứ tự từ điển ngược (thử độ dài đoạn từ lớn xuống nhỏ, trừ số cách phân đoạn phần còn lại). Với nhiều truy vấn, cần tìm cách đi nhanh qua những bước mà lựa chọn là hiển nhiên.

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.