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个字母出现的次数。
而且某一位要放置的字母出现多次，那么只需要计算一次就好，因为所有的排列都是一模一样的。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list> 10 #include <set> 11 #include <map> 12 using namespace std; 13 #define INF 0x3f3f3f3f 14 typedef long long LL; 15 16 char s[30]; 17 int a[30]; 18 LL fac[30]; 19 void init() 20 { 21 fac[0] = 1; 22 for(int i = 1; i < 21; i++) 23 fac[i] = fac[i-1] * i; 24 } 25 int main() 26 { 27 int t, n; 28 init(); 29 scanf("%d", &t); 30 for(int ca = 1; ca <= t; ca++) 31 { 32 scanf("%s %d", s, &n); 33 int len = strlen(s); 34 memset(a, 0, sizeof(a)); 35 for(int i = 0; i < len ; i++) 36 a[s[i]-'a']++; 37 LL res = fac[len]; 38 for(int i = 0; i < 26; i++)//相同字母没有区别 39 if(a[i]) res /= fac[a[i]]; 40 if(res < n) 41 { 42 printf("Case %d: Impossible ", ca); 43 continue; 44 } 45 printf("Case %d: ", ca); 46 for(int i = 0; i < len; i++) 47 { 48 for(int j = 0; j < 26; j++) 49 { 50 if(a[j] == 0) continue; 51 a[j]--; 52 LL te = fac[len-i-1]; 53 for(int k = 0; k < 26; k++) 54 { 55 if(a[k]) te /= fac[a[k]]; 56 } 57 if(te >= n)//大于等于要得到的字典序，get 58 { 59 printf("%c", j+'a'); 60 break; 61 } 62 a[j]++; 63 n -= te;//比要得到的字典序小，当然减去 64 } 65 } 66 printf(" "); 67 } 68 return 0; 69 }