lightoj1060【康托逆展开】

可以先看些资料：http://blog.csdn.net/keyboarderqq/article/details/53388936

参考谷巨巨：http://blog.csdn.net/azx736420641/article/details/50982142

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int>PII;

const double eps=1e-5;

const double pi=acos(-1.0);

//const int mod=1e9+7;

const int INF=0x3f3f3f3f;

char s[25];

LL  f[25];

int a[30];

void init()

{

    f[0]=1;

    for(int i=1;i<=22;i++)

        f[i]=f[i-1]*i;

}

int main()

{

    init();

    int n,T,len,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s%d",s,&n);

        len=strlen(s);

        memset(a,0,sizeof(a));

        for(int i=0;i<len;i++)

            a[s[i]-'a']++;

        //计算总的方案数，采用除序法；

        LL temp=f[len];

        for(int i=0;i<26;i++)

            temp/=f[a[i]];

        printf("Case %d: ",cas++);

        if(temp<n)

        {

            puts("Impossible");

            continue;

        }

        for(int i=0;i<len;i++)

        {

            for(int j=0; j<26; j++)

            {

                if(!a[j])

                    continue;

                a[j]--;

                LL tmp=f[len-i-1];          //对于第i个位置为j，计算总排列数

                for(int k=0; k<26; k++)     //除序法计算方案数

                    tmp/=f[a[k]];

                if(n<=tmp)          //如果方案数已超，一定是字母 j ;

                {

                    printf("%c",'a'+j);

                    break;

                }

                n-=tmp; //减去，肯定是别的字母

                a[j]++;

            }

        }

        puts("");

    }

    return 0;

}

巴特西

lightoj1060【康托逆展开】

最新文章

热门文章