浅念づ昔夜's Blog

Like author, like book.

0%

康托展开

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

简介

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。本文内容包括逆康托展开。

分析

康托展开

设全排列的元素总数为 nn。一个全排列对应的自然数，为此全排列在所有全排列中的字典序。下面以 n=5n=5，排列为 43512 为例，展示康托展开的公式如何得到。

对于首位 4，有 3 个元素比它小。后面的 4 位共有 4!4! 种排列。则必有 3⋅4!3\cdot 4! 种排列字典序小于原排列。若首位选择锁定 4 ，与所求排列保持相同，则考虑第二位 3 ，余下共有 2 个元素比它小。则又可得 2⋅3!2\cdot 3! 种合法排列。以此类推，得所求字典序：

X=3⋅4!+2⋅3!+2⋅2!+0⋅1!+0⋅0!+1X = 3\cdot 4! + 2\cdot 3! + 2\cdot 2! + 0\cdot 1! + 0\cdot 0! + 1

加 11 是因为要算上原排列自身。

推广到所有 nn，得到康托展开的公式：

X=∑k=1nak⋅(n−k)!+1X = \sum^{n}_{k=1}a_k\cdot (n-k)! + 1

aia_i 为原排列在第 ii 位之后，有多少个元素小于第 ii 位的元素。

code

朴素算法 Θ(n2)\Theta(n^2)。可用树状数组优化至 Θ(nlog⁡n)\Theta(n\log n)。

洛谷 P5367 【模板】康托展开

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define N 1000010
using namespace std;
typedef long long ll;
const ll mod = 998244353;

template <typename T> inline void read(T &x)
{
    x = 0; T f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

ll n, a[N], tr[N], ans, fac[N], can[N];

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

void add(ll x, ll val) 
{
    while (x <= n) {
        tr[x] += val;
        x += lowbit(x);
    }
}

ll query(ll x) 
{
    ll res = 0;
    while (x) {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}

void pre()
{
    fac[1] = fac[0] = 1;
    for (int i = 2; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    for (int i = n; i >= 1; i--) {
        can[i] = query(a[i]) * fac[n - i] % mod;
        add(a[i], 1);
    }
}

int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    pre();
    for (int i = 1; i <= n; i++)
        ans = (ans + can[i]) % mod;
    printf("%lld", ans + 1);
    return 0;
}

逆康托展开

逆康托展开是自然数对全排列的映射。下列做一个简单的推导：

n!=(n−1)(n−1)!+(n−1)!n! = (n-1)(n-1)!+(n-1)!

(n−1)!=(n−2)(n−2)!+(n−2)!(n-1)!=(n-2)(n-2)!+(n-2)!

于是对 n!n! 展开得

n!=∑k=1n−1k⋅k!+1n!=\sum^{n-1}_{k=1}k\cdot k!+1

即

n!>∑k=1n−1k⋅k!n!>\sum^{n-1}_{k=1}k\cdot k!

因此在保证 ai≤na_i\le n 的条件下，可对自然数 XX 分解为

X=∑k=1nak⋅(n−k)!+1X = \sum^{n}_{k=1}a_k\cdot (n-k)! + 1

且 aia_i 的排列唯一。

我们可用类似进制转换的依次作商取余的办法求出所求排列。

代码简单，从略。