康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩.
而对于一个序列，其所有排列按照字典序排序的顺序从小到大编号, 康拓展开就是用于计算这种排列在其顺序中的位置.

举个栗子╰(°▽°)╯
对于序列{1,3,2}, 它的顺序位于其所有排列的第2位, 前一位为{1,2,3}.

其公式如下:

其中 T 为其排列的顺序, A_i 为序列中第 i 个元素, n 为序列总长度.

我们可以看到, 其中需要计算n!, 这一步可以通过打表来优化时间复杂度, 而当n!过大的时候, 就需要大整数计算了.

康托展开的逆运算

因为康托展开是一个双射, 那么一个合法的 T 值必定对应一个唯一的序列, 也就是说可以反向计算顺序为 T 的序列.

1.输入n, T
2.计算第i位对应的值(i从1开始):
    a)将T-1，意为前面有T-1个排列
    b)currI = T/(n-i)!, currI即为当前位数
    c)如果currI已经被使用过,那么currI++
    d)currM = T%(n-i)!, currM为剩下的数
    e)T = currM
3.输出所有的currI

那么直接来道题叭:CodeVS 2972 - 选课

但是这道题...数据并不是很强...只有三个监测点

资料参考 Joseph Galante:Generalized Cantor Expansions