康托の复习笔记
概念
摘自百度百科。
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
康托展开
逐位计算，考虑一个排列 \(1\sim i-1\) 位已经确定的贡献。如果 \(i\) 位置填了比 \(a_i\) 小的数，\(i+1\sim n\) 无论怎么填都是小的。所以可以得出计算公式：
\[\sum_{i=1}^n\left(\sum_{j=i+1}^n a_j<a_i\right)\times(n-i)!+1
\]
\]
中间那个东西可以用树状数组维护。
逆康托展开
观察到 \(\left(\sum_{j=i+1}^n a_j<a_i\right)<n-i\)，这也恰恰说明逆展开是唯一的。
对于每一位都可以计算出后面小于当前位的数量，因为一些数在之前已经用过了，所以要在树状数组上二分。
P1088 [NOIP2004 普及组] 火星人
如何做到 \(O(n\log n)\)？
\(n\) 太大了，转排名加上 \(m\) 再转排列不现实。
康拓展开的实质是什么？
如果遇见过一些奇怪的进制应该可以想到，康拓展开其实就是阶乘进制，只不过每个位置的系数比较特殊，并不直接是该位置上的数值，而是后面数值小于该位置数值的个数。
考虑维护系数，显然一种排列可以对应多个系数。
初始直接将 \(n\) 位置的系数加上 \(m\)。
接着就是要在保证排名不变的情况下调整系数至还原后排列合法。
先来看还原的过程。从前往后，和逆康托展开一样搞，系数即逆康托展开中除出来的个数。
那就只要保证 \(i\) 位置的系数是小于等于 \(n-i\) 的即可。
诶好像证明了是阶乘进制
不断进位就做完啦！
