康拓展开在求字典序问题上是一个十分强大的算法
首先，康拓展开是形如以下的式子
X=an∗(n−1)!+an−1∗(n−2)!+...+a1∗0!下面介绍一下此式在康拓展开中的含义
首先我们假设有一个长为n的字符串s，下标从0开始ai的值是在后i-1个字符中，其中比s[n-i]小的字符个数那么在此字符串在所有的排列中，字典序比此字符串小的有X个那么我们就可以快速解决一些字典序的问题
首先就是如上所说的求有多少个比这个字典序小的字符串数，代码如下
@Frosero #include <iostream> #include <cstring> using namespace std; long long mul(long long n){ if(n == 0 || n == 1) return n; return n * mul(n - 1); } long long KT(string &s){ //康拓展开 long long ans = 0; for(string::size_type i=0;i<s.size();i++){ long long ai = 0; for(string::size_type j=i+1;j<s.size();j++){ //计算ai if(s[i] > s[j]){ ai++; } } ans += ai * mul(s.size() - i - 1); } return ans; //若想求此字符串是第几小，则返回ans+1 } int main(){ string s = "CAB"; cout << KT(s); return 0; }康拓展开的逆用：快速找到第K个字典序的排列
方法：我们可以从高位到低位依次推断系数an，代码如下
@Frosero #include <iostream> #include <cstring> #include <set> #include <map> #include <cstdlib> #include <algorithm> #include <cstdio> #include <cmath> #include <stack> #include <queue> #include <vector> #define eps 1e-6 #define INF 0x3f3f3f3f #define LL long long using namespace std; long long mul(long long n){ if(n == 0 || n == 1) return 1; return n * mul(n - 1); } bool used[25]; void inv_KT(long long k,long long len,long long *a){ k--; memset(used,false,sizeof(used)); int tot = 0; for(int i=len-1;i>=0;i--){ int ai = k / mul(i); //确定最高位的系数ai int cnt = 0; for(int j=1;;j++)if(!used[j]){ //只有未被使用的数字才加入计数cnt if(cnt == ai){ a[tot++] = j; used[j] = true; //used[i]表示数字i是否在前面已经被使用 break; //若已被使用则used[i]标记为true } cnt++; } k = k % mul(i); //确定余数，继续进行后面的运算 } } int main(){ long long K = 5,len = 3,a[25]; inv_KT(K,len,a); for(int i=0;i<len;i++) cout<<a[i]<<" "; return 0; }一些补充：
目测这个算法只能计算没有重复字符的字符串C++中长度为20的字符串几乎是我们能处理的极限(不考虑高精度，或者用JAVA写肯定是壕无压力处理几万长的字符串)这里我们用数字来表示示例的顺序，实际中只要建立数字和字符的映射关系即可。这也是这个算法之所以强大之所在！转载于:https://www.cnblogs.com/ScratchingBear/p/5345843.html
