康托展开笔记

变进制数

定义

所谓变进制数，就是每一位进制不一定相同的数，形式化的来讲：
对于一个变进制 $A =\{a_1,a_2, a_3 ... a_n\}$ , $a_i$ 表示第 $i$ 位的一个 $1$ 相当于第 $i-1$ 位的一个 $a_i$ .特别的, $a_1 = 1$

变进制数转十进制数

就像 $k$ 进制数转十进制数一样, 设变进制数第 $i$ 位是 $b_i$, 那么转成十进制就是 $\sum_{i=1}^{n}b_i\prod_{j=1}^{i}a_j$

十进制数转变进制数

就像十进制数转 $k$ 进制数一样, 设变进制数第 $i$ 位是 $b_i$, 十进制数为 $d$, 那么转成变进制就是 $b_i = d 对从 n 到 i + 1 的每一个 a_i 取模， 再处以 a_i 的值下取整$

康托展开

用于求一个排列的排名.
对于排列的每一位，分别考虑有多少排列之前位和这个排列一样，这一位比这个排列小， 显然这样可以做到不重不漏
设排列是一个 $1-n$ 的排列，对于排列的第 $i$ 位，比它小的排列的数量就是 $1-n$ 中第 $i$ 位以及之前没有出现的比第 $i$ 位的数小的数的数量， 再乘上 $(n-i)!$
就是先使这一位比原来小，后面几位随便排。
最后把答案加起来就行。
通过树状数组维护比当前数小的没有出现的数的数量可以优化到 $O(n\lg n)$