DDOSvoid's Blog

康托展开

发表于 更新于 分类于
本文字数： 529 阅读时长 ≈ 1 分钟

简介

大概就是所有排列向整数的一个映射？

我们对于每个排列 $p$，可以计算其排名为 $1+\sum_{i=1}^n a_i\times (n-i)!$，其中 $a_i$ 为 $\sum_{j=i+1}^n[p_j<p_i]$

这个式子很简单，我们考虑如果一个排列小于当前计算的排列

那么他必定是前面 $i$ 位与当前排列相同，然后第 $i+1$ 位小于当前排列，后面随便排，$i$ 可以取 $0$ 到 $n-1$

相应的，我们可以根据这个东西得到一个 $O(n\log n)$ 算法

逆康拓展开

大概就是给出排名求排列

具体做法就是康拓展开反过来，我们只需要每次除 $(n-i)!$ 即可

1
2
3
4
5
6
7
8
9
10
11
bool use[maxn]; int ans[maxn];
void rev_contor(ll rk) {
    fill(use + 1, use + n + 1, 0); --rk;
    for (int i = 1; i <= n; ++i) {
        ll s = rk / fac[n - i] + 1, v = 0; rk %= fac[n - i];
        for (int j = 1; j <= n; ++j) {
            v += !use[j];
            if (v == s) { ans[i] = j; use[j] = 1; break; }
        }
    } 
}