对于一个集合内所有元素的排列，康拓展开是一个无冲突的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]= {'','','','','',''};
LL w[siz];
bool vis[siz];
cantor()
{
w[]=;
for(int i=; i<siz; i++)
w[i]=w[i-]*i;
}
void init()
{
for(int i=; i<siz; i++)
vis[i]=false;
}
LL makeCanto(string s)
{
init();
LL rec=;
for(int i=; i<siz; i++)
{
int d=;
for(int j=; j<siz; j++)
{
if(vis[j])
continue;
if(c[j]!=s[i])d++;
else
{
vis[j]=true;
break;
}
}
rec+=w[siz-i-]*d;
}
return rec;
}
string recover(LL val)
{
init();
string s="";
for(int i=siz-; i>=; i--)
{
LL te=val/w[i];
val%=w[i];
for(int j=,cnt=-; j<siz; j++)
{
if(vis[j])continue;
else cnt++;
if(cnt==te&&!vis[j])
{
s+=c[j];
vis[j]=true;
break;
}
}
}
return s;
}
} ;