康托展开

首先我们知道对于一个有n个元素的集合，有

\[\sum_{i=1}^n A_{n}^i =n!\]

我们将该集合全排列按字典序从小到大排序

那么我们就可以用一个数x表示该集合的某个排列在全排列中的位置

显然变化的最高位（记作\(maxn\)）上的数每增加1，后面的\((maxn-1)\)位就跑了一次全排列，也就是整个排列变化了\((n-1)!\)次，对于后面的数位我们依此类推，访问过的数字不用再管，因为我们只关心局部的相对大小关系

最后因为位置从1计数,\(++x\)

void cntur(){    memset(vis,0,sizeof(vis));long long x=0;    for(int i=n;i;--i) scanf("%d",&cup[i]);    for(int i=n-1;i;--i){        int cnt=0;        for(int j=1;j

康托展开的逆运算

由于康托展开是集合排列同连续整数的一一映射，我们可以用已知的康托展开求原排列

void recntur(){    memset(vis,0,sizeof(vis));    long long x;scanf("%lld",&x);--x;    for(int i=n-1;i;--i){        int tmp=x/fac[i],cnt=0;x%=fac[i];        for(int j=1;j<=n;++j){            if(!vis[j]) ++cnt;            if(cnt>tmp){cup[i+1]=j,vis[j]=1;break;}        }    }for(int i=1;i<=n;++i) if(!vis[i]){cup[1]=i;break;}    for(int i=n;i;--i) printf("%d ",cup[i]);puts("");    return;}

模板题：