代码模板-康托展开

康托展开

康托展开用于求 $1 \sim n$ 的排列在所有排列中的字典序排名，用树状数组维护未使用过的数中比当前数小的个数。预处理阶乘 $O(n)$，单次展开 $O(n \log n)$。

#define int long long
const int N = 1e6 + 5, mod = 998244353;

int n, a[N];
int jc[N];      // 阶乘表
int t[N];       // 树状数组

void add(int id) {
    for (int i = id; i <= n; i += (i & (-i))) t[i]++;
}

int query(int id) {
    int ret = 0;
    for (int i = id; i; i -= (i & (-i))) ret += t[i];
    return ret;
}

int cantor() {
    // 预处理阶乘
    jc[0] = 1;
    for (int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % mod;

    int res = 0;
    // 倒序枚举，统计 a[i] 后方比它小的数的个数
    for (int i = n; i; i--) {
        int ca = query(a[i]);           // 已经出现（即已在后方）且比 a[i] 小的个数
        res = (res + ca * jc[n - i]) % mod;
        add(a[i]);
    }
    // res 是比当前排列小的排列数，排名为 res + 1
    return res + 1;
}

提示

树状数组维护的是值域上每个数是否已经出现（从后往前扫描），query(a[i]) 统计的是已经扫过的数中比 $a[i]$ 小的个数，即原公式中的 $c_{a[i]}$。

相关笔记：【组合数学】康托展开学习笔记