UVA_11027
首先如果要组成回文串，最多只能有一种字母是奇数个。
然后我们不妨设要找第N个回文串，那么自然先挑字典序最小的一对放在两端，这样算一下这种情况一共有p种，如果p<N，说明当前应该放字典序更大一点的，于是我们令N=N-p，然后再尝试下一种方法。
这样如果第一位尝试了所有的情况都始终没有p>N的话，就说明一共都没有N个这么多的回文串，自然就输出XXX，但放第一位的时候如果某刻出现p>=N的话，那么便必然有解。于是再按照上面的方法递归去安排后续中间的回文串即可，同时这时也可以开始打印方案了，因为必然有解。
当然，也要注意一下只有一个字符的情况。
#include<stdio.h>
#include<string.h>
int a[30], flag;
long long int N;
char b[50];
long long int A(int k)
{
int i;
long long int ans = 1;
for(i = 2; i <= k; i ++)
ans *= i;
return ans;
}
long long int C(int m, int n)
{
int i;
long long int ans = 1;
if(m - n < n)
n = m - n;
for(i = 1; i <= n; i ++)
ans = ans * (m - i + 1) / i;
return ans;
}
long long int calculate(int sur)
{
int i;
long long int ans = 1;
while(sur)
{
ans *= sur;
-- sur;
}
for(i = 1; i <= 26; i ++)
if(a[i])
ans /= A(a[i]);
return ans;
}
void dfs(int sur, long long int total)
{
int i, j, k;
long long int ans;
if(sur == 0)
{
if(total > 1)
printf("XXX");
else if(flag)
printf("%c", flag + 'a' - 1);
return ;
}
for(i = 1; i <= 26; i ++)
if(a[i])
{
-- a[i];
ans = calculate(sur - 1);
if(ans < total)
total -= ans;
else
{
printf("%c", i + 'a' - 1);
dfs(sur - 1, total);
printf("%c", i + 'a' - 1);
return ;
}
++ a[i];
}
printf("XXX");
}
void solve()
{
int i, j, k;
k = flag = 0;
memset(a, 0, sizeof(a));
for(i = 0; b[i]; i ++)
a[b[i] - 'a' + 1] ++;
for(i = 1; i <= 26; i ++)
if(a[i] % 2)
{
flag = i;
k ++;
}
if(k > 1)
{
printf("XXX");
return ;
}
k = 0;
for(i = 1; i <= 26; i ++)
{
a[i] /= 2;
k += a[i];
}
dfs(k, N);
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
{
scanf("%s%lld", b, &N);
printf("Case %d: ", tt + 1);
solve();
printf("\n");
}
return 0;
}