天天看点

我排第几个康托展开



我排第几个

时间限制: 1000 ms  |  内存限制: 65535 KB 难度: 3

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

第一行有一个整数n(0<n<=10000);

随后有n行,每行是一个排列;

输出
输出一个整数m,占一行,m表示排列是第几位;
样例输入
3
abcdefghijkl
hgebkflacdji
gfkedhjblcia      
样例输出
1
302715242
260726926      
康托展开:      

康托展开

康托展开 康托展开就是一种特殊的哈希函数,它的使用范围是对于n个数的排列进行状态的压缩和存储,例如要对9的全排列进行判重.没有必要 开一个10^9的数组,同时内存也不允许开到那么大的数组.对此,有人提出了优化,即对于一个n的排列数,没有必要开到10^n,因为在一个排列中每个数只出现一次,所以只要前n-1位确定了,前N位就确定了. 但是以上的想法仍不是可行的,因为N可以很大,例如15,所以便引入了康托展开:只需要确定这个排列在总的排列情况中是第几小的就可以了. 例如:我想知道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!是康托展开. 下面给出康托展开的代码:
int              hash(s[12])              {              int              ktzk=0;              for              (              int              i=1;i<=12;i++)              {              int              tot=0;              for              (              int              j=i+1;j<=12;j++)              if              (s[j]>s[i]) tot++;              ktzk+=(tot*mi[12-i]);              //mi[I]数组中记录了i的阶乘.              }              return              ktzk;              }           
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int a[12]= {39916800,3628800,362880,40320,5040,720,120,24,6,2,1,1};//记录0,1,2,3,4,5,6,7,8,9,10,11的阶乘
char b[1000];
int c[1000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",b);
        int l;
        l=strlen(b);
        for(int i=0; i<l; i++)
        {
            c[i]=b[i]-'a';
        }
        int p;
        int sum=0;
        for(int i=0; i<l; i++)
        {
            p=0;
            for(int j=11; j>i; j--)
            {
                if(c[i]>c[j])
                {
                    p++;
                }
            }
            sum+=p*a[i];
        }
        printf("%d\n",sum+1);
    }
}