【数论系列】康托展开

由上可以看出： a[i] 表示第i位后面比他小的元素的个数，也就是可以排列在 i 位上的还没有确定的自由的元素。对于第i位的可能取值，前i位的数字已经确定，且在全排列中每一个数字只能出现一次，只需要比较i位后面的数字比i位数字小的有几个，即可知道第i位的可能取值。此排列的序号为：（1）+（2）＋…＋（9）+ 1

3. 代码模板

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long LL; int n; int num[1000]; LL fact[1000]; //int fact[] = {1,1,2,6,24,120,720,5040,40320,};//定义阶乘表0！ ~ 9！ void getMaxir()//获取0！~n! { fact[0] = 1; for(int i = 1;i<=n;i++){ fact[i] = fact[i-1]*i; } } LL Contor(int *s)//康拓展开 { LL sum = 0;//记录总的在s之前数目 for(int i = 0;i<n;i++){//枚举固定第i位 int cnt = 0;//记录比第i位小的元素 for(int j = i+1;j<n;j++){//在i后面（剩下未被选择自由元素集合）寻找比第i位小的元素个数 if(s[j]<s[i])cnt++; } sum += (fact[n-i-1]*cnt);//累计 } return sum+1;//返回次序 } int main() { while(scanf("%d",&n)!=EOF){ for(int i = 0;i<n;i++){ scanf("%d",&num[i]); } getMaxir(); LL ans = Contor(num); printf("%lld\n",ans); } return 0; }

4. 功能作用

（1）压缩判重：把大排列数/字符串转化为1~int或者long long之内的唯一标识数字，作为状态用数组标记判重。例如用在A* 或者 BFS搜索中标记状态。

bool Contor(Node &s) { int code = 0; for(int i = 0;i<9;i++){ int cnt = 0; for(int j = i+1;j<9;j++){ if(s.state[j]<s.state[i])cnt++; } code+=(fact[8-i]*cnt); } if(vis[code])return false; //当前状态已标记 vis[code] = 1; return true; }

（2）次序求解：用于求字符串或者排列中的第几个问题

二. 逆康拓展开

1. 逆康托展开的定义

康托展开是一个全排列到一个自然数的双射，因此是可逆的。也就是说我们也可以根据全排列的次序编号，逆向求出该全排列的表达式。其求解过程正是康托展开式的逆向计算过程，类似于进制转换，不断 %(n-i)! & /(n-1)! 就可以还原出原排列。举例如下：

已知在12345的全排列中，排列组合34152的排名次序是第62。那么由上述的计算过程可以容易的逆推回来，具体过程如下：

（1）初始化将 62-1 = 61，即比34152小的全排列组合数目为61个

（2）用 61 / 4! = 2余13，说明比首位小的数有2个，此时排列元素集合为{1,2,3,4,5} ，所以首位为3。

（3）用 13 / 3! = 2余1，说明在第二位之后小于第二位的数有2个，此时排列元素集合为{1,2,4,5} ，所以第二位为4。

（4）用 1 / 2! = 0余1，说明在第三位之后没有小于第三位的数，此时排列元素集合为{1,2,5}，所以第三位为1。

（5）用 1 / 1! = 1余0，说明在第四位之后小于第四位的数有1个，此时排列元素集合为{2,5}，所以第四位为5。

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

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

2. 代码模板

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1000 + 7; int num[maxn]; bool vis[maxn]; int fact[] = {1,1,2,6,24,120,720,5040,40320,};//阶乘表0！ ~ 9！ //在n位数字全排列中，第x位的逆康托展开 void DeContor(int n,int x){ x-=1;//初始化全排列数目 for(int i = 1;i <= n;i++){ int k = x/fact[n-i]; x %= fact[n-i]; //查找1-n中未被选择且第k+1小的元素 int sum = 0; for(int j = 1;j <= n;j++){ if(!vis[j])sum++; if(sum == k+1){ vis[j] = 1; num[i-1] = j; break; } } } } int main() { int n,index; while(scanf("%d%d",&n,&index)!=EOF){ memset(vis,0,sizeof(vis)); DeContor(n,index); for(int i = 0;i < n;i++){ if(i!=0)printf(" "); printf("%d",num[i]); } printf("\n"); } return 0; }

三. 康托展开树状数组优化

在上述康托展开中，在i后面（剩下未被选择自由元素集合）寻找比第i位小的元素个数即计算 a[i] 这步操作时，我们使用了遍历的方法使得整个康托展开的复杂度为 O(n^2)。这步操作其实可以简化为：

问题：求数组（数组元素值是连续的1~n）中在当前下标 i 处，i < j 且 A[i] > A[j] 的逆序对数目，并且每个位置会随时更新。

这不就是典型的树状数组求逆序对问题吗，因此我们可以引入树状数组来维护优化康托展开，时间复杂度降为O(nlogn)。注意数组值非连续时，要进行离散化。

例题（洛谷 P5367） :

#include <iostream> #include<bits/stdc++.h> #define mod  #define lowbit(x) x&(-x) using namespace std; typedef long long LL; const int maxn =  + 7; int n,num[maxn],fact[maxn],c[maxn]; void getMaxir()//获取0！~n! { fact[0] = 1; for(int i = 1;i<=n;i++){ fact[i] = (fact[i-1]*i)%mod; } } void Update(int x,int value){ for(int i = x;i<=n;i+=lowbit(i)){ c[i] = (c[i]+value)%mod; } } LL Query(int x){ LL sum = 0; for(int i = x;i>0;i-=lowbit(i)){ sum = (sum+c[i])%mod; } return sum; } LL Contor()//康拓展开 { LL sum = 0; for(int i = 1;i<=n;i++){ sum = (sum + fact[n-i]*Query(num[i]-1)%mod)%mod;//查询 1~num[i]-1 之间能使用的数字还有几个，累计 Update(num[i],-1); //更新当前数字为已使用状态 } return (sum+1)%mod;//返回次序 } int main() { scanf("%d",&n); memset(c,0,sizeof(c)); //获取乘阶项 getMaxir(); //输入排列数组，并初始化树状数组各元素使用次数为1 for(int i = 1;i<=n;i++){ scanf("%d",&num[i]); Update(i,1); } printf("%lld\n",Contor()); return 0; }

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/118582.html

【数论系列】 康托展开

一. 康托展开

1. 康托展开定义

2. 康托展开举例