对于一个集合内所有元素的排列，康拓展开是一个无冲突的hash法。其规则便是将排列在逻辑上排好序，然后每个排列的序号即是hash值。

关键就在如何快速求出序号和快速还原啦。

首先我们确定一好集合内各元素的大小关系，然后开始处理。

生成：

对于一个排列（长度为n），我们要算出它前面有多少比它小的序列，如果序号从0开始，那么这个数字就是它的序号。

有点类似数位DP的处理，我们从最高位看起（设位x），如果一个排列的最高位比它小，那么这个排列一定比它小。

所以设集合中比x小的元素有k个，如果最高位确定，那么后面的几位可以随意排列，显然有(n-1)!种，那么一共就有k*(n-1)!种。

最高位确定了，我们就考虑最高位相等时次高位的情况，处理方法是类似的，但是在计算k的时候，因为原先用过的数字已经不能出现在后面了，所以统计比x'小的元素时不能把他们算进去，然后乘上(n-2)!即可。

每一位都这样处理，就可以不重不漏啦。

 

复原：

因为不存在冲突，在系数k不超过n-i时，这个多项式的值我们可以用除法和取余来实现复原。

设hash值为val

k=val/(n-1)!

val%=(n-1)!//写成val-=k*(n-1)!也是可以的

k即是比当前位小的元素个数，val把当前项减去。

即可还原排列了。

 

代码：

class cantor{public:#define siz 6    char c[siz]= {
   '1','2','3','4','5','6'};    LL w[siz];    bool vis[siz];    cantor()    {        w[0]=1;        for(int i=1; i
     
      =0; i--)        {            LL te=val/w[i];            val%=w[i];            for(int j=0,cnt=-1; j