康托展开了解一下—NPC

首先，度娘镇楼：康托展开是一个全排列到一个的，常用于构建时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

注：双射=》既满足单射（一个变量对应一个函数值）又满足满射（对于所有函数值都有一个以上变量与之对应）

公式如下：

 

其中,ai为整数,并且。表示的是位于位置i后面的数小于的个数（未出现的数）

举例：

n = 5  对于45321这个排列数中，有4的后面比4小的数有3、2、1，共3个，5后有3、2、1，3后2、1，2后1，1后面就没有了。

因此有：3*4!+3*3!+2*2!+1*1!+0*0! = 95

所以比45321小的排列有95个，即45321为第96个排列；

康托展开的逆运算

既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

       对于n = 5给出61可以算出起排列组合为34152。具体过程如下：

用 61 / 4! = 2余13，说明a5=2,说明比首位小的数有2个，所以首位为3。

用 13 / 3! = 2余1，说明a4=2，说明在第二位之后小于第二位的数有2个，则第二位为4。

用 1 / 2! = 0余1，说明a3=0，说明在第三位之后没有小于第三位的数，则第三位为1。

用 1 / 1! = 1余0，说明a2=1，说明在第二位之后小于第四位的数有1个，则第四位为5。

最后一位自然就是剩下的数2。

通过以上分析，所求排列组合为 34152

 

所以康托展开在OI中什么鬼用法？

一个排列对应一个值且值是连续的自然数 当然压空间啊 例题：，

板子代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 int shu[10];//记录数字排列 6 bool vis[10];//标记是否出现过 7 int jc[10]= {
   1,1,2,6,24,120,720,5040,40320};//预处理阶乘值 8 int KT(int *a,int n){ 9     int num = 0;10     for(int i = 1;i <= n;i++){11         int cnt = 0;12         for(int j = i+1;j <= n;j++){
   //统计有多少比第i位小的数13             if(shu[i] > shu[j]) cnt++;14         }15         num += cnt*jc[n-i];16     }17     return num;18 }19 void re_KT(int num,int len){20     int i,j,t;21     memset(vis,0,sizeof(vis));22     --num;23     for(i = 0;i < len;i++){24         t = num/jc[len-i-1];25         for(j = 1;j <= len;j++){26             if(!vis[j]){27                 if(t == 0) break;28                 --t;29             }30         }31         shu[i] = j;32         vis[j] = true;33         num %= jc[len-i-1];34     }35 }36 int main()37 {38     int len;39     scanf("%d",&len);40     for(int i = 1;i<=len;i++){41         scanf("%d",&shu[i]);42     }43     int KT_num = KT(shu,len);44     printf("%d\n",KT_num);45     re_KT(KT_num+1,len);//康托展开值表示比它的有多少个排列数46     for(int i = 0;i
       
      
     

1 52 1 4 3 2 5

1 142 1 4 3 2 5