一年多前遇到差不多的题目http://acm.fafu.edu.cn/problem.php?id=1427。
一开始我还用搜索。。后来那时意外找到一个不重复全排列的计算公式：M!/(N1!*N2!*...*Nn!)，
然后就靠自己YY出解法，搞了好几天，最后向学长要了数据，然后迷迷糊糊调了，终于AC了。
后来才知道当时想的解法类似于逆康托展开，只是逆康托展开是对于没有重复元素全排列而言，不过有没有重复元素都一个样。
而现在做这题很顺，因为思路很清晰了，另外这做法和数论DP的统计部分有相似之处。
#include<cstdio>
#include<cstring>
using namespace std;
long long fact[]={};
long long calu(int n,int *cnt){
long long res=fact[n];
for(int i=; i<; ++i) res/=fact[cnt[i]];
return res;
}
int main(){
for(int i=; i<; ++i) fact[i]=fact[i-]*i;
char str[];
long long n;
int t;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%s%lld",str,&n);
int sn=strlen(str),cnt[]={};
for(int i=; i<sn; ++i) ++cnt[str[i]-'a'];
if(calu(sn,cnt)<n){
printf("Case %d: Impossible\n",cse);
continue;
}
printf("Case %d: ",cse);
for(int i=; i<sn; ++i){
for(int j=; j<; ++j){
if(cnt[j]==) continue;
--cnt[j];
if(n>calu(sn-i-,cnt)){
n-=calu(sn-i-,cnt);
++cnt[j];
}else{
putchar(j+'a');
break;
}
}
}
putchar('\n');
}
return ;
}