寂静的角落 星空在前,路在脚下
康托展开
发布于: 2021-07-07 更新于: 2021-07-09 分类于: OI > 数学 阅读次数: 

反正乱推就完事了。

康托展开

康托展开可以求一个 $1 \sim n$ 的任意排列的排名。

变进制数

字面意思。

定义

给定无穷数集 $S = {a_0, a_1, a_2, \cdots, a_n, \cdots}, a_0 = 1$,定义变进制数为第 $i$ 位的单位是上一位单位的 $a_i$ 倍。

则有变进制数 $(A)_S = \overline{x_n x_{n - 1} \cdots x_1 x_0}, 0 \le x_i < a_{i + 1}$。

类似于其他不变进制数,如十进制为每位满 $10$ 进 $1$,而变进制数则为第 $i$ 位满 $a_{i + 1}$ 进 $1$。

进制转换

将变进制数转化为十进制数也与不变进制数类似,如二进制转十进制为第 $i$ 位乘上 $2^i$,而变进制数则为乘上 $\prod_{j = 0}^i a_j$,即:

$$\begin{aligned} A_{10} &= \sum_{i = 0}^n (x_i \prod_{j = 0}^i a_j) \\ &= x_n \prod_{i = 0}^n a_i + x_{n - 1} \prod_{i = 0}^{n - 1} + \cdots + x_1 a_1 a_0 + x_0 a_0 \end{aligned}$$

将不变进制数转变进制数,同理,用短除法除每一位 $a_i$ 然后取余数为答案。

$\rm \color{green}code$

点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
// 变进制数转十进制数
template <typename T>
inline T Stod(T *a, T *x, int n) {
T A = 0;
for (int i = n; ~i; --i) A = (A + x[i]) * a[i];
return A;
}
// 十进制数转变进制数
template <typename T>
inline void dtoS(T A, T *a, T *x) {
for (int i = 0; A; ++i) x[i] = A % a[i + 1], A /= a[i + 1];
}

广义康托展开

内容

广义康托展开即给定两个变进制 $S_1, S_2$ 和 $(A)_{S_1}$,求 $(A)_{S_2}$。

做法

我们现在不知道怎么将一个变进制数转换为另一个变进制数,但我们知道如何将一个变进制数转为十进制数和如何将十进制数转为变进制数,于是我们就可以将十进制数作为中转来将一个变进制数转换为另一个变进制数。

$\rm \color{green}code$

点击查看代码
1
2
3
4
5
6
template <typename T>
inline void StoS(T *a1, T *x1, T *a2, T *x2, int n) {
T A = 0;
for (int i = n; ~i; --i) A = (A + x1[i]) * a1[i];
for (int i = 0; A; ++i) x2[i] = A % a2[i + 1], A /= a2[i + 1];
}

阶乘进制数

定义

$a_i = i(i \neq 0)$ 的变进制数 $(A)_! = \overline{x_n x_{n - 1} \cdots x_1 x_0}$ 称为阶乘进制数。

则阶乘进制转十进制有

$$\begin{aligned} A_{10} &= \sum_{i = 0}^n (x_i \prod_{j = 0}^i a_j) = \sum_{i = 0}^n (x_i \prod_{j = 0}^i (j, j \neq 0 : 1, j = 0)) \\ &= \sum_{i = 0}^n (x_i i!) = x_n n! + x_{n - 1} (n - 1)! + \cdot + x_2 2! + x_1 1! + x_0 1 \end{aligned}$$

康托展开

内容

将任意十进制数转为阶乘进制数。

做法

直接套公式即可。

$\rm \color{green}code$

点击查看代码
1
2
3
4
template <typename T>
inline void cantor_exp(T A, T *x) {
for (int i = 0; A; ++i) x[i] = A % (i + 1), A /= (i + 1);
}

逆康托展开

内容

字面意思,将阶乘进制数转十进制。

做法

直接套公式即可。

$\rm \color{green}code$

点击查看代码
1
2
3
4
5
6
template <typename T>
inline T inv_cantor_exp(T *x, int n) {
T A = 0;
for (int i = n; ~i; --i) A = (A + x[i]) * (i == 0 ? 1 : i);
return A;
}

排列与阶乘进制数

内容

任何一个 $1, \cdots, n$ 的排列都对应一个唯一的阶乘进制数。

那么我们可以使 $x_i$ 为 $p_i$ 在后缀 ${p_i, p_{i + 1}, \cdots, p_n}$ 中的排名,排名从 $0$ 开始。

这样我们就可以将排列转变为阶乘进制数。

但是直接这样算的复杂度是 $\Omicron(n^2)$ 的,太高,我们需要更低的复杂度。

观察计算过程,发现最消耗时间的是查询后缀排名这一步。

动态查询排名可以用平衡树,复杂度为 $\Omicron(\log n)$,但是编程复杂程度太高。

树状数组是 $\Omicron(\log^2 n)$ 的。

考虑线段树,我们可以在线段树上二分查询排名,复杂度也是 $\Omicron(\log n)$,但是易实现。

还有树状数组上二分,不会。

这样总复杂度为 $\Omicron(n \log n)$。

代码见下面例题

例题:[NOIP2004 普及组] 火星人

提交地址:洛谷 Luogu1088

题目大意

给定 $1, \cdots, n (n \le 10^3)$ 的排列 $p_1, p_2, \cdots, p_n$ 和正整数 $m (m \le 100)$。

设当前排列的排名为 $rank$,求排名为 $rank + m$ 的排列。

做法

原题数据范围很小,我们只要暴力枚举排列即可。

$\rm \color{green}code$

点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
int n, m;
scanf("%d", &n);
scanf("%d", &m);
int s[n];
for (int i = 0; i < n; i++) scanf("%d", &s[i]);
for (int i = 0; i < m; i++) next_permutation(s, s + n);
for (int i = 0; i < n; i++) printf("%d ", s[i]);
return 0;
}

Bonus

更改数据范围为 $n \le 10^5, k \le 10^{18}$。

做法

现在暴力过不去了,考虑康托展开,我们直接展开为一个阶乘进制数,然后加上 $m$ 再转回去就好了,复杂度是 $\Omicron(n \log n)$ 的。

$\rm \color{green}code$

点击查看代码
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
59
60
61
62
63
64
65
66
67
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
// 线段树
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline int mid(int l, int r) { return (l + r) >> 1; }
ll c[maxn << 2];
inline void pushup(int p) { c[p] = c[ls(p)] + c[rs(p)]; }
void plus(int p, int l, int r, int t, ll x) {
if (l == r) {
c[p] += x;
return;
}
int m = mid(l, r);
if (t <= m)
plus(ls(p), l, m, t, x);
else
plus(rs(p), m + 1, r, t, x);
pushup(p);
}
// 查询和
ll query_sum(int p, int l, int r, int ql, int qr) {
if (qr < l || r < ql)
return 0;
else if (ql <= l && r <= qr)
return c[p];
else {
int m = mid(l, r);
ll res = 0;
res += query_sum(ls(p), l, m, ql, qr);
res += query_sum(rs(p), m + 1, r, ql, qr);
return res;
}
}
// 查询排名
ll query_rank(int p, int l, int r, ll cnt) {
if (l == r) return l;
int m = mid(l, r);
return cnt <= c[ls(p)] ? query_rank(ls(p), l, m, cnt)
: query_rank(rs(p), m + 1, r, cnt - c[ls(p)]);
}
int n, dlt;
ll x[maxn];
int main() {
scanf("%d%d", &n, &dlt);
for (int i = 1; i <= n; ++i) scanf("%lld", &x[i]);
// 转换为阶乘进制数,注意是倒着的
for (int i = n; i; --i) {
plus(1, 1, n, x[i], 1);
x[i] = query_sum(1, 1, n, 1, x[i]) - 1;
}
// 加上 m,处理进位
x[n] += dlt;
for (int i = n, j = 1; i && x[i] >= j; --i, ++j) {
x[i - 1] += x[i] / j;
x[i] %= j;
}
// 转回去
for (int i = 1; i <= n; ++i) {
x[i] = query_rank(1, 1, n, x[i] + 1);
plus(1, 1, n, x[i], -1);
}
for (int i = 1; i <= n; ++i) printf("%lld ", x[i]);
return 0;
}

后面没写完。

本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证