康托展开

康托展开可以用来求一个 的任意排列的排名。

什么是排列的排名

把 的所有排列按字典序排序，这个排列的位次就是它的排名。

时间复杂度

康托展开可以在 的复杂度内求出一个排列的排名，在用到 树状数组 优化时可以做到 。

实现

因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。

比如 的排列，，因为在第 位出现不同，则 的排名在 前面。

示例

我们知道长为 的排列 大于以 为第一位的任何排列，以 为第一位的 的排列有 种。这是非常好理解的。但是我们对第二位的 而言，它大于 第一位与这个排列相同的，而这一位比 小的 所有排列。不过我们要注意的是，这一位不仅要比 小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为 或 ，第一位为 的所有排列都比它要小，数量为 。

按照这样统计下去，答案就是 。注意我们统计的是排名，因此最前面要 。

注意到我们每次要用到 当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就可以了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <cstring>
#include <iostream>
using namespace std;
constexpr int MOD = 998244353;
using ll = long long;
int n, x, d[1000005];
ll fac[1000005], ans;

int lowbit(int x) { return x & -x; }

void modify(int x, int o) {
  while (x <= n) {
    d[x] += o;
    x += lowbit(x);
  }
}

int query(int x) {
  int ret = 0;
  while (x >= 1) {
    ret += d[x];
    x -= lowbit(x);
  }
  return ret;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    d[i] = lowbit(i);                 // O(n) 建树
    fac[i] = (fac[i - 1] * i) % MOD;  // 预处理阶乘
  }
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    modify(x, -1);
    ans = (ans + ll(query(x) * fac[n - i]) % MOD) % MOD;
  }
  cout << ans + 1 << '\n';
}

逆康托展开

因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。

如果我们知道一个排列的排名，就可以推出这个排列。因为 是严格大于 的，所以可以认为对于长度为 的排列，排名 除以 向下取整就是有多少个数小于这个排列的第一位。

示例

同样是上面展开的例子。首先让 ， 代表着有多少个排列比这个排列小。，有一个数小于它，所以第一位是 。

此时让排名减去 得到 ，，有 个数小于它，去掉已经存在的 ，这一位是 。

，，有一个数小于它，那么这一位就是 。

让 ，有一个数小于它，这一位是剩下来的第二位，，剩下一位就是 。即 。

实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第 个没有被选上的数，这里也可以用线段树维护，时间复杂度为 。

本页面最近更新：2024/10/5 17:45:55，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, gavinliu266, gi-b716, Great-designer, hjsjhn, Ir1d, MegaOwIer, Tiphereth-A, wjy-yy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用