康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。以下称第x个全排列是都是指由小到大的顺序。

公式

${X=a_{n}(n-1)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!}$

其中,$a_i$为整数,并且$0\leq a_{i}<i,1\leq i\leq n$

举例

例如，3 5 7 4 1 2 9 6 8 展开为 98884。因为$X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884$

解释：

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!

以此类推，直至0*0!

用途

显然，n位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出唯一的一个排列。

康托展开的逆运算

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

如n=5,x=96时：

>

首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1) 用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4. 用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5. 用5去除2!得到2余1，类似地，这一位是3. 用1去除1!得到1余0，这一位是2. 最后一位只能是1. 所以这个数是45321.

按以上方法可以得出通用的算法。

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

样例输入

3
abcdefghijkl
hgebkflacdji
gfkedhjblcia

样例输出

1
302715242
260726926

代码:

#include <bits/stdc++.h>//nyoj139
using namespace std;
int jc[13]= {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
int get_num(string s)
{
    int len=s.size();
    int ans=0;
    for(int i=0; i<len; i++)
    {
        int num=0;
        for(int j=i+1; j<len; j++)
            if(s[i]>s[j])
                num++;
        ans+=num*jc[len-i-1];
    }
    return ans;
}
int main()
{
    int t;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>s;
        cout<<get_num(s)+1<<endl;//如果下标从0开始则不+1
    }
    return 0;
}

镜像问题逆展开：

#include <bits/stdc++.h>//nyoj143
using namespace std;
int jc[13]= {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};
int num[13];//num[i]存储从小到大第i个未用过的字母编号
void init()
{
    for(int i=0; i<13; i++)
        num[i]=i;
}
string get_string(int cnt)//逆展开
{
    string ans="";
    for(int i=0; i<12; i++)
    {
        int tmp=cnt/jc[11-i];
        ans+=num[tmp]+'a';
        for(int j=tmp; j<11; j++)
            num[j]=num[j+1];
        cnt%=jc[11-i];
    }
    return ans;
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        init();
        cout<<get_string(n-1)<<endl;
    }
    return 0;
}