康托展开可以用来求一个 的任意排列的排名。
什么是排列的排名？
把 的所有排列按字典序排序，这个排列的位次就是它的排名。
时间复杂度？
康托展开可以在 的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到 。
怎么实现？
因为排列是按字典序排名的，因此越靠前的数字优先级越高。也就是说如果两个排列的某一位之前的数字都相同，那么如果这一位如果不相同，就按这一位排序。
比如 的排列，，因为在第 位出现不同，则 的排名在 前面。
举个栗子
我们知道长为 的排列 大于以 为第一位的任何排列，以 为第一位的 的排列有 种。这是非常好理解的。但是我们对第二位的 而言，它大于 第一位与这个排列相同的，而这一位比 小的 所有排列。不过我们要注意的是，这一位不仅要比 小，还要满足没有在当前排列的前面出现过，不然统计就重复了。因此这一位为 或 ，第一位为 的所有排列都比它要小，数量为 。
按照这样统计下去，答案就是 。注意我们统计的是排名，因此最前面要 。
注意到我们每次要用到 当前有多少个小于它的数还没有出现，这里用树状数组统计比它小的数出现过的次数就可以了。
逆康托展开
因为排列的排名和排列是一一对应的，所以康托展开满足双射关系，是可逆的。可以通过类似上面的过程倒推回来。
如果我们知道一个排列的排名，就可以推出这个排列。因为 是严格大于 的，所以可以认为对于长度为 的排列，排名 除以 向下取整就是有多少个数小于这个排列的第一位。
引用上面展开的例子
首先让 ， 代表着有多少个排列比这个排列小。，有一个数小于它，所以第一位是 。
此时让排名减去 得到 ，，有 个数小于它，去掉已经存在的 ，这一位是 。
，，有一个数小于它，那么这一位就是 。
让 ，有一个数小于它，这一位是剩下来的第二位，，剩下一位就是 。即 。
实际上我们得到了形如 有两个数小于它 这一结论，就知道它是当前第 个没有被选上的数，这里也可以用线段树维护，时间复杂度为 。
/*
* 康托展开式是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩
* 康托展开实质：计算当前排列在所有由小到大的全排列中的名次，因此可逆
* 输入正整数 N ，输入从 1 到 N 的某个排列，求该排列在全排列中的排名位置
* 如输入 N 为 3 ，全排列为 123 132 213 231 312 321
* 输入排列 2 1 3 ， 2 1 3 在全排列中排第三 ，而康托展开值是该排列前有多少个排列
*/
/*举例：输入 5763214，计算其序号
* ①ans = 0 , tmp = 0 , 字符串长度为 7
* ②第一个数 5 ，进入循环，遍历 7 6 3 2 1 4 ，其中有 3 2 1 共三个数比 5 小，所以 tmp = 3
* ③ans = ans + tmp * factorial[6] = 0 + 3 * 6!
* ④第二次循环，开始看第二个数 7 ，tmp = 0
* ⑤遍历 6 3 2 1 4 ，其中有 6 3 2 1 4 共五个数比 7 小，所以 tmp = 5
* ⑥ans = ans + tmp * factorial[5] = 3 * 6! + 5 * 5!
* ⑦依次类推………………
*/
#include<iostream>
#include<string>
using namespace std;
int factorial[20];//存放阶乘, 0! 1! 2! 3! …………
void get_fac(string str)//获得阶乘
{
int n = str.size();//也可以用 .length， n 为输入的排列位数，如 51342 是五位，则这里获得五个阶乘
factorial[0] = factorial[1] = 1;// 0！和 1！都是 1
for (int i = 2; i < n; ++i)
{
factorial[i] = factorial[i - 1] * i;
}
return;
}
int cantor(string str)//康托展开
{
int ans = 1;//序号，12345……康托展开是 0 ，计算时结果为 0 ，ans 无法记录（增加），但其算一个序号，所以 ans 从 1 开始
int len = str.size();//字符串长度
for (int i = 0; i < len; ++i)
{
int tmp = 0;//在下面的循环记录第 i 位的后面比其小的数的个数
for (int j = i + 1; j < len; ++j)//从第 i 位的后面一位开始遍历后面的数
{
if (str[i] > str[j]) ++tmp;//如果后面的某位数小于第 i 位数，则符合康托展开要求
}
ans += tmp * factorial[len - 1 - i];//因为阶乘数组中是 0！ 1！ 2！ 3！ …… 所以依次从后面往前乘，然后开始外循环的第二次循环，tmp 重新赋值为 0
/*符合康托展开公式
X = An * (n - 1)! + An-1 * (n - 2)! + …… + A2 * 1! + A1 * 0!
An 是第 i 位后面的数中比其小的数的个数
*/
}
return ans;
}
int main()
{
string str;
cin >> str;//输入排列
get_fac(str);
cout << cantor(str) << endl;
return 0;
}