### 1. 康托展开 (Cantor Expansion)
**用途：** 给定一个排列，计算它是所有全排列中字典序第几个（通常排名从 0 开始计数）。

**公式：**
$$X = a_1(n-1)! + a_2(n-2)! + \dots + a_n(0)!$$
其中 $a_i$ 表示：在当前未使用的数字中，比当前位数字小的数字个数。

**例：求 $\{2, 1, 3\}$ 的排名**
1.  第一位是 $2$，右边比 $2$ 小的有 $\{1\}$，共 1 个，即 $a_1 = 1$。
2.  第二位是 $1$，右边比 $1$ 小的有 $0$ 个，即 $a_2 = 0$。
3.  第三位是 $3$，右边比 $3$ 小的有 $0$ 个，即 $a_3 = 0$。
$X = 1 \times 2! + 0 \times 1! + 0 \times 0! = 2 + 0 + 0 = 2$。
由于排名从 0 开始，所以 $\{2, 1, 3\}$ 是第 2 个（即字典序第 3 个，前两个是 `123, 132`）。

---

### 2. 逆康托展开 (Inverse Cantor Expansion)
**用途：** 给定排名 $X$ 和元素个数 $n$，求出该排列。

**步骤（以 $n=5, X=95$ 为例）：**
1.  **确定第一位：** $95 \div 4! = 3 \dots 23$。说明有 3 个数比第一位小，在 $\{1, 2, 3, 4, 5\}$ 中选第 $3+1$ 个数，即 **4**。剩余 $\{1, 2, 3, 5\}$。
2.  **确定第二位：** $23 \div 3! = 3 \dots 5$。说明有 3 个数比第二位小，在剩余数中选第 $3+1$ 个数，即 **5**。剩余 $\{1, 2, 3\}$。
3.  **确定第三位：** $5 \div 2! = 2 \dots 1$。说明有 2 个数比第三位小，在剩余数中选第 $2+1$ 个数，即 **3**。剩余 $\{1, 2\}$。
4.  **确定第四位：** $1 \div 1! = 1 \dots 0$。说明有 1 个数比第四位小，在剩余数中选第 $1+1$ 个数，即 **2**。剩余 $\{1\}$。
5.  **确定第五位：** 剩下的最后一个数 **1**。
**结果：** `4 5 3 2 1`。

---

### 3. 代码实现 (C++)
在实际编写程序时，需要预处理阶乘，并使用一个标记数组（或 `vector`）来寻找“第 $k$ 个未使用的数”。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long fact[20]; // 预处理阶乘

// 初始化阶乘
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
}

// 1. 康托展开：求排列的排名 (从0开始)
long long cantor(vector<int>& p, int n) {
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = i + 1; j < n; j++) {
            if (p[j] < p[i]) count++; // 计算右边比当前位小的数
        }
        ans += count * fact[n - 1 - i];
    }
    return ans;
}

// 2. 逆康托展开：根据排名求排列
vector<int> reverseCantor(long long x, int n) {
    vector<int> res;
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i); // 可用的数字池

for (int i = n - 1; i >= 0; i--) {
        int index = x / fact[i]; // 有几个数比当前位小
        x %= fact[i];
        res.push_back(nums[index]); // 找到对应的数
        nums.erase(nums.begin() + index); // 移除已使用的数
    }
    return res;
}

int main() {
    int n = 5;
    init(n);

// 示例1
    vector<int> p = {2, 1, 3};
    cout << "Rank of {2,1,3}: " << cantor(p, 3) << endl;

// 示例2
    long long x = 95;
    vector<int> res = reverseCantor(x, 5);
    cout << "95th permutation of 5: ";
    for (int v : res) cout << v << " ";
    cout << endl;

return 0;
}
```

### 4. 优化点
*   **时间复杂度：** 
    *   上述 `cantor` 是 $O(n^2)$。如果 $n$ 很大（如 $10^5$），可以使用**树状数组 (Binary Indexed Tree)** 优化到 $O(n \log n)$。
    *   上述 `reverseCantor` 中 `vector::erase` 是 $O(n)$，总时间 $O(n^2)$。同样可以用 **线段树/树状数组 + 二分** 优化到 $O(n \log n)$。
*   **溢出：** $20!$ 已经超出了 `long long` 的范围。如果 $n > 20$，通常题目会要求对大数取模，或者排列长度不会那么大。

1. 康托展开 (Cantor Expansion)

用途： 给定一个排列，计算它是所有全排列中字典序第几个（通常排名从 0 开始计数）。

公式： $$X = a_1(n-1)! + a_2(n-2)! + \dots + a_n(0)!$$ 其中 $a_i$ 表示：在当前未使用的数字中，比当前位数字小的数字个数。

例：求 ${2, 1, 3}$ 的排名 1. 第一位是 $2$，右边比 $2$ 小的有 ${1}$，共 1 个，即 $a_1 = 1$。 2. 第二位是 $1$，右边比 $1$ 小的有 $0$ 个，即 $a_2 = 0$。 3. 第三位是 $3$，右边比 $3$ 小的有 $0$ 个，即 $a_3 = 0$。 $X = 1 \times 2! + 0 \times 1! + 0 \times 0! = 2 + 0 + 0 = 2$。由于排名从 0 开始，所以 ${2, 1, 3}$ 是第 2 个（即字典序第 3 个，前两个是 123, 132）。

2. 逆康托展开 (Inverse Cantor Expansion)

用途： 给定排名 $X$ 和元素个数 $n$，求出该排列。

步骤（以 $n=5, X=95$ 为例）： 1. 确定第一位： $95 \div 4! = 3 \dots 23$。说明有 3 个数比第一位小，在 ${1, 2, 3, 4, 5}$ 中选第 $3+1$ 个数，即 4。剩余 ${1, 2, 3, 5}$。 2. 确定第二位： $23 \div 3! = 3 \dots 5$。说明有 3 个数比第二位小，在剩余数中选第 $3+1$ 个数，即 5。剩余 ${1, 2, 3}$。 3. 确定第三位： $5 \div 2! = 2 \dots 1$。说明有 2 个数比第三位小，在剩余数中选第 $2+1$ 个数，即 3。剩余 ${1, 2}$。 4. 确定第四位： $1 \div 1! = 1 \dots 0$。说明有 1 个数比第四位小，在剩余数中选第 $1+1$ 个数，即 2。剩余 ${1}$。 5. 确定第五位： 剩下的最后一个数 1。 结果： 4 5 3 2 1。

3. 代码实现 (C++)

在实际编写程序时，需要预处理阶乘，并使用一个标记数组（或 vector）来寻找“第 $k$ 个未使用的数”。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long fact[20]; // 预处理阶乘

// 初始化阶乘
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
}

// 1. 康托展开：求排列的排名 (从0开始)
long long cantor(vector<int>& p, int n) {
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = i + 1; j < n; j++) {
            if (p[j] < p[i]) count++; // 计算右边比当前位小的数
        }
        ans += count * fact[n - 1 - i];
    }
    return ans;
}

// 2. 逆康托展开：根据排名求排列
vector<int> reverseCantor(long long x, int n) {
    vector<int> res;
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i); // 可用的数字池

    for (int i = n - 1; i >= 0; i--) {
        int index = x / fact[i]; // 有几个数比当前位小
        x %= fact[i];
        res.push_back(nums[index]); // 找到对应的数
        nums.erase(nums.begin() + index); // 移除已使用的数
    }
    return res;
}

int main() {
    int n = 5;
    init(n);

    // 示例1
    vector<int> p = {2, 1, 3};
    cout << "Rank of {2,1,3}: " << cantor(p, 3) << endl;

    // 示例2
    long long x = 95;
    vector<int> res = reverseCantor(x, 5);
    cout << "95th permutation of 5: ";
    for (int v : res) cout << v << " ";
    cout << endl;

    return 0;
}

4. 优化点

时间复杂度：
- 上述 cantor 是 $O(n^2)$。如果 $n$ 很大（如 $10^5$），可以使用树状数组 (Binary Indexed Tree) 优化到 $O(n \log n)$。
- 上述 reverseCantor 中 vector::erase 是 $O(n)$，总时间 $O(n^2)$。同样可以用 线段树/树状数组 + 二分 优化到 $O(n \log n)$。
溢出： $20!$ 已经超出了 long long 的范围。如果 $n > 20$，通常题目会要求对大数取模，或者排列长度不会那么大。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com