lightoj1060_組合數學

http://lightoj.com/volume_showproblem.php?problem=1060

有一些用尼康托展開http://blog.csdn.net/niushuai666/article/details/6611131，簡單的尼康托，每個字母多個數的還不會

組合數學解看起來比較簡單

給定一個字符串和k，求字符串第k大字典序的排列...

康拓逆展開...可以求沒有重復元素的第k個排列，有重復的話，方法是一樣的，只是求解方案數變了。

由單純的階乘變為len！/cnt[i]!（0<=i<26），cnt[i]為第i個字母出現的次數。

而且某一位要放置的字母出現多次，那么只需要計算一次就好，因為所有的排列都是一模一樣的。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <ctime>
#include <queue>
#include <list>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;

char s[30];
int a[30];
LL fac[30];
void init()
{
    fac[0] = 1;
    for(int i = 1; i < 21; i++)
        fac[i] = fac[i-1] * i;
}
int main()
{
    int t, n;
    init();
    scanf("%d", &t);
    for(int ca = 1; ca <= t; ca++)
    {
        scanf("%s %d", s, &n);
        int len = strlen(s);
        memset(a, 0, sizeof(a));
        for(int i = 0; i < len ; i++)
            a[s[i]-'a']++;
        LL res = fac[len];
        for(int i = 0; i < 26; i++)//相同字母沒有區別
            if(a[i]) res /= fac[a[i]];
        if(res < n)
        {
            printf("Case %d: Impossible\n", ca);
            continue;
        }
        printf("Case %d: ", ca);
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < 26; j++)
            {
                if(a[j] == 0) continue;
                a[j]--;
                LL te = fac[len-i-1];
                for(int k = 0; k < 26; k++)
                {
                    if(a[k]) te /= fac[a[k]];
                }
                if(te >= n)//大于等于要得到的字典序，get
                {
                    printf("%c", j+'a');
                    break;
                }
                a[j]++;   
                n -= te;//比要得到的字典序小，當然減去               
            }
        }   
        printf("\n");     
    }
    return 0;
}

?