我排第几个
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？
输入
第一行有一个整数n（0<n<=10000）;
随后有n行，每行是一个排列；
输出
输出一个整数m，占一行，m表示排列是第几位；
样例输入
3
abcdefghijkl
hgebkflacdji
gfkedhjblcia
样例输出
1
302715242
260726926
解题思路：
1、 用康托展开，找出第几个。
康托展开：
1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。
代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。
他们间的对应关系可由康托展开来找到。
如我想知道321是{1,2,3}中第几个大的数可以这样考虑 ：
第一位是3，当第一位的数小于3时，那排列数小于321 如 123、 213 ，小于3的数有1、2 。所以有2*2!个。再看小于第二位2的：小于2的数只有一个就是1 ，所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。 2*2!+1*1!+0*0!就是康托展开。
再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1和2，但1已经在第一位了，所以只有一个数2 1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数 0*1! ，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。
程序代码：
#include<stdio.h>
#include<string.h>
int main()
{
int a[12];
int n,i,j,k,b[12];
char c[15];
a[0]=1;
j=1;
for(i=1;i<12;i++)
{
j*=i;
a[i]=j; // 把 1~~12的阶乘保存在对应的数组里面。
//printf("%d ",a[i]);
}
while(scanf("%d",&n)!=EOF)
{
memset(b,0,sizeof(b)); //数组 b 清零。
scanf("%s",c);
for(i=0;i<12;i++)
{
for(j=i+1;j<12;j++)
{
if(c[i]>c[j])
b[i]++; // 比后面的字母大的有几个
}
}
k=0;
for(i=0;i<12;i++)
{
k=k+b[i]*a[11-i]; // 康拓展开。
}
printf("%d\n",k+1); //输出结果要加以。
}
return 0;
}