nyoj 139 我排第几个(康拓展开)

我排第几个

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

3abcdefghijklhgebkflacdjigfkedhjblcia样例输出
1302715242
260726926
AC代码如下：
#include<cstdio>using namespace std;const int maxn=12+2;char s[maxn];int stratum(int n){    //求阶层	int sum=1;	for(int i=1;i<=n;i++){		sum*=i;	}	return sum;}int cantor(){        //康拓展开	int sum=0;for(int i=0;i<12;i++){	int temp=0;	for(int j=i+1;j<12;j++)		if(s[i]>s[j])temp++; 	sum+=temp*stratum(11-i);   }   return sum;} int main(){	int n;	scanf("%d",&n);	while(n--){		scanf("%s",s);		int cnt=cantor();		PRintf("%d/n",cnt+1);	}	return 0;} 
（1）康拓展开
　　所谓康拓展开是指把一个整数X展开成如下形式：
　　X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!。（其中，a为整数，并且0<=a[i]<i(1<=i<=n)）
（2）应用实例
　　{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个：123 132 213 231 312 321。他们间的对应关系可由康托展开来找到。
　　1324是{1,2,3,4}排列数中第几个大的数：　　第一位是1小于1的数没有，是0个 0*3! ；　　第二位是3小于3的数有1和2，但1已经在第一位了，即1未出现在前面的低位当中，所以只有一个数2 1*2! ；　　第三位是2小于2的数是1，但1在第一位，即1未出现在前面的低位当中，所以有0个数 0*1! ；　　所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。