康托展开是一种全排列到自然数的双射（映射）算法，简单来说，对于一个由 \(1 \sim n\) 共 \(n\) 个不重复数字构成的全排列，若按字典序将这 \(n!\) 种所有可能的排列从小到大进行排序（从第 \(0\) 个或第 \(1\) 个开始计）：

• 正向康托展开：输入一个排列，计算出它是字典序中的第几个排列（求解排列的字典序排名）。
• 逆康托展开：输入排名 \(k\)，还原出第 \(k\) 小的原始排列。

在算法竞赛中，康托展开常用于状态压缩与哈希。例如著名的八数码问题，网格中数字的排列即为一个全排列。通过康托展开，可以将任意一个 \(n\) 阶排列无冲突地映射为一个闭区间 \([0,n!-1]\) 之间的唯一整数，从而可以作为状态数组的下标，支撑搜索操作。

对于一个长度为 \(n\) 的排列 \(P = (p_1, p_2, \dots, p_n)\)，其康托展开值 \(X\)（表示比当前排列字典序更小的排列数量，即从 \(0\) 开始计数时的排名）计算公式为 \(X = a_1 \cdot (n-1)! + a_2 \cdot (n-2)! + \dots + a_i \cdot (n-i)! + \dots + a_n \cdot 0!\)，简写为 \(X = \sum\limits_{i=1}^{n} a_i \cdot (n-i)!\)，其中：

• \(a_i\) 表示在当前位置 \(i\) 右侧（即 \(p_{i+1} \dots p_n\) 中），比 \(p_i\) 严格小的元素的个数。
• \((n-i)!\) 表示位置 \(i\) 后面的剩余 \(n-i\) 个位置全排列的总方案数。

以 \(n=5\) 的排列 \(P = (3, 4, 1, 5, 2)\) 为例，求其从 \(0\) 开始计数的字典序排名 \(X\)：

1. 第 \(1\) 位 \(p_1 = 3\)，右侧剩余元素为 \(\{4, 1, 5, 2\}\)，比 \(3\) 小的元素有 \(\{1, 2\}\)，共 \(a_1 = 2\) 个，贡献为 \(a_1 \cdot (5-1)! = 2 \cdot 4! = 2 \cdot 24 = 48\)。
2. 第 \(2\) 位 \(p_2 = 4\)，右侧剩余元素为 \(\{1, 5, 2\}\)，比 \(4\) 小的元素有 \(\{1, 2\}\)，共 \(a_2 = 2\) 个，贡献为 \(a_2 \cdot (5-2)! = 2 \cdot 3! = 2 \cdot 6 = 12\)。
3. 第 \(3\) 位 \(p_3 = 1\)，右侧剩余元素为 \(\{5, 2\}\)，比 \(1\) 小的元素有 \(0\) 个，即 \(a_3 = 0\)，贡献为 \(a_3 \cdot (5-3)! = 0 \cdot 2! = 0\)。
4. 第 \(4\) 位 \(p_4 = 5\)，右侧剩余元素为 \(\{2\}\)，比 \(5\) 小的元素有 \(\{2\}\)，共 \(a_4 = 1\) 个，贡献为 \(a_4 \cdot (5-4)! = 1 \cdot 1! = 1 \cdot 1 = 1\)。
5. 第 \(5\) 位 \(p_5 = 2\)，右侧无剩余元素，比其小的元素个数 \(a_5 = 0\)，贡献为 \(a_5 \cdot 0! = 0 \cdot 1 = 0\)。

计算总和得到 \(X = 48 + 12 + 0 + 1 + 0 = 61\)，这说明排列 \((3, 4, 1, 5, 2)\) 的康托展开值为 \(61\)，即前面有 \(61\) 个更小的排列，它自身是字典序第 \(62\) 小的排列。

逆康托展开是康托展开的逆过程：已知阶数 \(n\) 与排名值 \(X\)，还原出原始的排列 \(P\)。

假设给定 \(n=5, X=61\)，还原步骤如下：

1. 计算第 \(1\) 位：\(a_1 = \lfloor X / (5-1)! \rfloor = \lfloor 61 / 24 \rfloor = 2\)，更新 \(X = X \pmod{24} = 61 \pmod{24} = 13\)，\(a_1=2\) 意味着在当前可用数字集合 \(\{1, 2, 3, 4, 5\}\) 中，第 \(1\) 位数字前有 \(2\) 个比它小的数，因此选择索引为 \(2\) 的元素（从 \(0\) 开始计数），即数字 \(3\)，剩余可用数字为 \(\{1, 2, 4, 5\}\)。
2. 计算第 \(2\) 位：\(a_2 = \lfloor 13 / (5-2)! \rfloor = \lfloor 13 / 6 \rfloor = 2\)，更新 \(X = 13 \pmod 6 = 1\)，从剩余数字 \(\{1, 2, 4, 5\}\) 中，选择索引为 \(2\) 的数字，即数字 \(4\)，剩余可用数字为 \(\{1, 2, 5\}\)。
3. 计算第 \(3\) 位：\(a_3 = \lfloor 1 / (5-3)! \rfloor = \lfloor 1 / 2 \rfloor = 0\)，更新 \(X = 1 \pmod 2 = 1\)，从剩余数字 \(\{1, 2, 5\}\) 中，选择索引为 \(0\) 的元素，即数字 \(1\)，剩余可用数字为 \(\{2, 5\}\)。
4. 计算第 \(4\) 位：\(a_4 = \lfloor 1 / (5-4)! \rfloor = \lfloor 1 / 1 \rfloor = 1\)，更新 \(X = 1 \pmod 1 = 0\)，从剩余数字 \(\{2, 5\}\) 中，选择索引为 \(1\) 的元素，即数字 \(5\)，剩余可用数字为 \(\{2\}\)。
5. 计算第 \(5\) 位：填入最后剩下的数字 \(2\)。

还原得到的排列为 \((3, 4, 1, 5, 2)\)，与原输入完全一致。

在计算 \(a_i\) 时，如果对于每个 \(p_i\) 都用一层循环去扫描其右侧的所有元素，那么康托展开的时间复杂度为 \(O(n^2)\)。在算法竞赛中，当 \(n\) 达到 \(10^5\) 级别，\(O(n^2)\) 会引发超时。

计算 \(a_i\) 的实质是求序列中位于位置 \(i\) 右侧且数值比 \(p_i\) 小的元素个数（本质上是求逆序对的变体），因此可以用树状数组优化到 \(O(n \log n)\)。

例题：P5367 【模板】康托展开

给定一个长度为 \(N \ (1 \le N \le 10^6)\) 的排列（有数字 \(1 \sim N\) 组成），求该排列在所有 \(1 \sim N\) 的全排列中按字典序由小到大排列的排名。由于答案可能非常大，最终结果需要对 \(998244353\) 取模。

#include <iostream>
using namespace std;
using ll = long long;
const int N = (int)1e6 + 5;
const int MOD = 998244353;
int n;
int f[N]; // 存储阶乘模 MOD 的值
int bit[N]; // 树状数组，维护当前数字的使用状态
// 树状数组 lowbit 函数
int lowbit(int x) {
    return x & (-x);
}
// 树状数组单点修改
void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        bit[i] += v;
    }
}
// 树状数组前缀和查询
int query(int x) {
    int s = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        s += bit[i];
    }
    return s;
}
int main()
{
    cin >> n;
    // 预处理阶乘并初始化树状数组
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = (ll)f[i - 1] * i % MOD;
        add(i, 1);
    }
    int ans = 1;
    // 遍历每一个位置并计算康托展开值
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        // 查询尚未使用的数字中小于 x 的数量
        int s = query(x - 1);
        // 累加当前位的贡献 s * (n - i)!
        ans += (ll)s * f[n - i] % MOD; ans %= MOD;
        // 将当前数字 x 标记为已使用
        add(x, -1);
    }
    cout << ans << "\n";
    return 0;
}