偏个题：算阶乘int可以到12，long long可以到20（12和20，好记）
背景知识
康托展开
原理
n个数字或者字符全排列（每个元素只用一次），从小到大按照字典序排列好，从0开始给他们编号，从字符串映射到编号就是康托展开。
从最高位向低位计算：
- 若取小于最高位的数字，则后面任意取都是小于这个排列的
- 若取相同数字，就比较下一位数字，若取小于的数后面同样任意排列，但是注意前面两个数字不能再用
总之，就是小于当前位的数字个数乘以剩下的元素的全排列
代码
#include<bitsstdc++.h>
/*******打出1-n的阶乘表*******/
int f[20];
void jie_cheng(int n)
{
f[0] = f[1] = 1; // 0的阶乘为1
for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
/**************康托展开****************/
int kangtuo(string str)
{
int ans = 1; //注意，因为 12345 是算作0开始计算的，最后结果要把12345看作是第一个
int len = str.length();
for(int i = 0; i < len; i++){
int tmp = 0;//用来计数的
for(int j = i + 1; j < len; j++){
if(str[i] > str[j]) tmp++;
//计算str[i]是第几大的数，或者说计算有几个比他小的数
}
ans += tmp * f[len - i - 1];
}
return ans;
}
int main()
{
jie_cheng(10);
string str = "52413";
cout<< kangtuo(str) << endl;
}逆康托展开
原理
就是已知编号和元素，倒推出来原排列。
显然编号和原排列一一对应，是双射，所以必然可逆
举例：假设五个元素，序号为61.
用 61 / 4! = 2余13，说明两个元素小于2,说明比首位小的数有2个，所以第5位位为3。
用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第4位为4。
用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第3位为1。
用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第2位为5。
通过以上分析，所求排列组合为 34152。
代码
#include<bits/stdc++.h>
using namespace std;
/*******打出1-n的阶乘表*******/
int f[20];
int x, num;
void jie_cheng(int n)
{
f[0] = f[1] = 1; // 0的阶乘为1
for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
/**************康托逆展开**************/
vector<char> vec; //存需要排列的字符
void rev_kangtuo(int k) //输出序号为 k 的字符序列
{
int n = vec.size(), len = 0;
string ans = "";
k--; // 算的时候是按 12345 是第0位
for(int i = 1; i <= n; i++){
int t = k / f[n - i]; // 第 i 位需要 第 t + 1 大的数
k %= f[n - i]; //剩下的几位需要提供的排列数
ans += vec[t] ; // vec[t] 就是第 t + 1 大的数
vec.erase(vec.begin() + t);
//用过就删了，不用vector用暴力也可以，就是说枚举，然后一个一个的比较大小，并记录有几个没用过的字符且字典序比它小
}
cout << ans << '\n';
}
/***************************************/
// 假设展开后不超过10位
int main()
{
jie_cheng(10); // 预处里好阶乘
scanf("%d", &x); // 输入需要逆展开的数字
/************康托逆展开***********/
for(int i = 1; i <= 10; i++)
{
if(x / f[i] == 0) // 求出 x 逆展开所需的最小的位数，方便下面的初始化
{
num = i;
break;
}
}
for(int i = 1; i <= num; i++) vec.push_back(i + '0'); //输入的位数只要不小于num就可以
rev_kangtuo(x);
}蓝桥杯题解代码
比较从上和下两个方向走的距离，取最小值
#include <bits/stdc++.h>
using namespace std;
/*******打出1-n的阶乘表*******/
long long f[25];
void jie_cheng(int n)
{
f[0] = f[1] = 1; // 0的阶乘为1
for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
/**************康托展开****************/
int kangtuo(string str)
{
long long ans = 1;
int len = 17;
for(int i = 0; i < len; i ++ ) {
int tmp = 0;//用来计数的
for(int j = i + 1; j < len; j ++ ) {
if(str[i] > str[j]) tmp ++ ;
//计算str[i]是第几大的数，或者说计算有几个比他小的数
}
ans += tmp * f[len - i - 1];
}
return ans;
}
int main()
{
jie_cheng(18);
string str1 = "aejcldbhpiogfqnkr", str2 = "ncfjboqiealhkrpgd";
long long n1 = kangtuo(str1);
long long n2 = kangtuo(str2);
long long sum1 = n2 - n1;
long long sum2 = f[17] - sum1;
long long sum = min(sum1, sum2);
cout<< sum << endl;
}