题解报告：NYOJ 题目139 我排第几个（康托展开）

描述

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

输入

第一行有一个整数n（0<n<=10000）;
随后有n行，每行是一个排列；

输出

输出一个整数m，占一行，m表示排列是第几位；

样例输入

3

abcdefghijkl

hgebkflacdji

gfkedhjblcia

样例输出

解题思路：康托展开：已知一个排列，求这个排列在全排列中是第几个。康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。那么，对于n个数的排列，康托展开为：$ X = a_n \times (n - 1)\! + a_{n-1} \times (n-2)\! + \cdots + a_2 \times 1\! + a_1 \times 0\! $，
其中 $a_i $ 表示第i个元素在未出现的元素（从小到大排列，并从0开始数）中排第几，（即第i+1位～第n位的元素中，也就是求后面有几个元素比第i个元素小）举个栗子：对于排列4213来说，4在4213中排第3，注意下标从0开始，2在213中排第1，1在13中排第0，3在3中排第0，即：$a_4 = 3, a_3 = 1, a_2 = 0, a_1 = 0$，这样就得到4213在所有排列中排在第X+1=20+1=21个。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 string str;int n;LL sum,num,len,fac[];

 LL getfac(int n){//打印阶乘表

     if(n==)return ;

     LL ans=;

     for(int i=;i<=n;++i)ans*=i;

     return ans;

 }

 int main(){

     for(int i=;i<;++i)fac[i]=getfac(i);//阶乘表

     while(cin>>n){

         while(n--){

             cin>>str;sum=;len=str.size();

             for(LL i=;i<len;++i){

                 num=;

                 for(LL j=i+;j<len;++j)

                     if(str[i]>str[j])num++;//找到还没出现且比当前字母小的字母个数，即在未出现的字母从小到大排列中排第几，注意下标从0开始

                 sum+=num*fac[len-i-];//累加康托展开每一项的值

             }

             cout<<sum+<<endl;//小于str的排列数有sum个，那么str就排在第sum+1个

         }

     }

     return ;

 }