【康托展开】

康托展开

首先我们知道对于一个有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<cup[i+1];++j) if(!vis[j]) ++cnt;
        x+=cnt*fac[i],vis[cup[i+1]]=1;
    }++x;printf("%lld\n",x);
    return;
}

康托展开的逆运算

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

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;
}

模板题:[USACO11FEB]牛线Cow Line