Warning

---

由于本博客作者实在是太弱啦，本篇文章可能存在大量的错误，漏洞，不规范，不合法之处。若您发现本文章所存在的任何问题，请您尽快在评论区指出，十分感谢！

另外，本文随意转载，但请注明出处。

问题

---

给出一个 n, 一个 1~n 的排列，问对于 1~n 的全排列，该排列按照字典序排名为多少.

n≤20

解答

---

此题需要用康拓展开解决，下面会给出一些介绍。

康拓展开是一种 n 的全排列与自然数空间 {0,1,2,..., n! -1} 的映射，简单的说，就是每一个全排列都有一个唯一的自然数与其对应，康托展开可以使我们找到这个自然数，显然，它是可逆的，我们可以通过逆康托展开找到某自然数对应的全排列.

所以显然，它是一种特殊的，毫不浪费空间的，无冲突的哈希函数，它具有如此优良的性质，那么它是如何映射的呢？下面给出公式：
$$X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!$$

a[i] 的含义将在随后的程序讲解中给出，下面我们尝试从本质上理解一下康托展开。如果不想看，完全可以跳过看应用部分，由于博主太弱，此处可能有模糊/不正确之处，欢迎神犇批判。

变进制

---

常见的进制有二进制、八进制、十进制、十六进制等，这些“常数进制”都是合法的计数方式，对于 p 进制数，采取“满 p 进 1”的方式，也就是说，p 进制数 K 可以表示为：

$$K=a[1]*p^{1}+a[2]*p^{2}+...+a[n]*p^{n}$$

然而，除此之外，我们还可以通过变进制来表示一个数，需要注意的是，并非随便一种变进制的策略都是合法的，下面给出一种合法的变进制数：

它的运算规则是这样的：对于第一位，满 2 进 1，第二位，满 3 进 1，以此类推，那么数 K 就可以这样表示：

$$K=a[1]*1!+a[2]*2!+...+a[n]*n!$$

这是很好理解的，但是我们需要证明这是一种合法的进位方式，我们假设数 K 为该规则下的变进制数，它的第 a[i] 位为 i+1，现在我们需要进位。通过下等式，我们可以知道这么做是合法的。即进位后的数 K‘依旧满足该规则，且 K'=K+1.

$$a[i]*i!=(i+1)*i!=1*(i+1)!$$

同时这种变进制规则具有如下显然的性质：

• (1) 当所有位 a[i] 均为 i 时，K 有最大值 (n+1)!-1
• (2) 当所有位 a[i] 均为 0 时，K 有最小值 0

那么我们就得到了一种合法的，具有良好性质的变进制数辣！

逆序对

---

这貌似不需要说... 知道其概念即可，下面直接引用百度百科定义

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

康拓展开

---

终于到这里啦~假设我们有 b[0],b[1]...b[n] 共 n+1 个互异的元素，这些元素存在某种排序关系使得 b[0]<b[1]...<b[n]，对它们任意排列，就有了 (n+1)! 种排列，我们记某排列其中第 i(1 ≤ i ≤ n) 个元素与它前面的 i 个元素构成的逆序对的对数为 di(0 ≤ di ≤ i)，这恰好是上述变进制数的每一位！因此，每个排列都可以按这种方式表示成一个 n 位变进制数 ~

并且，这样做还有一个很好的性质，那就是 n+1 个元素的全排列的每一个排列对应着一个不同的 n 位变进制数 。下面证明引用自 这里 ：(日后可能自己写一下更加易于理解的证明...)

对于全排列的任意两个不同的排列 p0,p1,p2,...,pn（排列 P）和 q0,q1,q2,...,qn（排列 Q），从后往前查找第一个不相同的元素，分别记为 pi 和 qi（0 < i <= n）。
（1）如果 qi > pi，那么,
如果在排列 Q 中 qi 之前的元素 x 与 qi 构成逆序对，即有 x > qi，则在排列 P 中 pi 之前也有相同元素 x > pi（因为 x > qi 且 qi > pi），即在排列 P 中 pi 之前的元素 x 也与 pi 构成逆序对，所以 pi 的逆序数大于等于 qi 的逆序数。又 qi 与 pi 在排列 P 中构成 pi 的逆序对，所以 pi 的逆序数大于 qi 的逆序数。
（2）同理，如果 pi > qi，那么 qi 的逆序数大于 pi 的逆序数。
因此，由（1）和（2）知，排列 P 和排列 Q 对应的变进制数至少有第 i 位不相同，即全排列的任意两个不同的排列具有不同的变进制数。至此，定理 1 得证。

这样，全排列就可以映射到自然数空间啦~

这就是康托展开

应用

---

我们重复一遍原始公式便于查阅$$X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!$$

如果你耐心的看完并理解了上述文字，那么代码的实现对你来说应该是不困难的，我们考虑当我们知道某排列时如何求它的排名：

若你看了上述文字，相信你已经知道 a[i] 是什么了，若没有，下面给出的信息对你来说可以当做结论来记忆理解.

a[i] 的含义即为第 i 位上的数所对应的逆序对个数，即上述 d[i]！

换一个角度，可以这样理解：

我们给出这样一个排列：3 5 7 4 1 2 9 6 8 ，它展开为 98884，因为 X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

针对第一位举例，排列的第一位是 3，比 3 小的数有两个，以这样的数开始的排列有 8! 个，因此第一项为 2*8!.

明白了做法，那么代码实现就是显然的啦~我们枚举每一位的逆序对个数，套用公式即可~

代码将会在文章的最后随着逆康托展开一起给出

逆康拓展开

---

 

在前文说到康托展开是可逆的，因为它是无冲突的，所以当我们给出 n 和某名次 m 时，我们也可以得到 m 对应的排列是什么，我们的做法和康托展开正好相反，只有套用公式解出 d[i] 的值即可，我们的做法在求某一位 d[i] 时，对当前 X 除以 (n-i)!，这样商即是要求的 d[i]，余数即是剩余项的和，直接进入下一步循环即可，但是在这里 细 (脑) 心 (残) 的读 (博) 者 (主) 可能会有一个小问题：如何保证上述做法的正确性呢？剩余项的和是否有可能大于等于当前项使得出现问题呢？自然，这是不可能的，下面博主给出 (需要感性理解的)(不严谨的)(愚蠢) 的证明：

我们思考构造一组当前项尽可能小，剩余项的和尽可能大的数据，显然，我们唯一可以控制的参数就是 d[i]，我们不难构造出如下的排列：1,n,n-1,n-2,...2

对于该式，如果上述做法依旧成立，那么其余情况不可能比此更糟了，那么我们需要证明的便是：$$n!> \sum_{i=1}^{n}(n-i)*(n-i)!$$

将每一项 ( n-i ) * ( n-i ) ! 拆成$$( n-i+1) * (n-i)! - 1*(n-i) !$$

那么原式就可以整理得：$$( 1!+2!+3!+...+n! )-( 0!+1!+...+( n-1 )! ) = n!-1 < n!$$

该做法成立，证毕~

有了 d[i]，想推出 a[i] 自然是很容易的啦~但是要注意，康托展开是对应 [0,(n-1)!] 间的自然数的，它包括 0，这意味着，我们通常意义上的从 1 开始的“名次”在进行逆康托展开前需要先-1...

下面给出代码：

例题

---

终于有了.... [USACO2011 Feb] Cow Line