链接：http://vjudge.net/problem/viewProblem.action?id=19602

描述：给出一个字符串，求重新排列后第n个回文串，若没有则输出”XXX“。

思路：组合数问题。

首先考虑什么时候有回文串。很简单，数量为奇数的字母不超过1个。且这个字母只能是在字符串的中间。

然后我们会发现，回文串的字典序就是字串前半部分的字典序。问题就转化成求字典序第n的字符串。于是我们可以试着模拟一下这个过程。首先把字典序最小的字母放在第一个位置，然后计算出后面字母的排列数，即固定下第一个位置后有多少种字符串，设这个数是Num。如果Num>=n，则第一个位置就确定了，继续考虑第二个位置；如果Num<n，则第一个位置的字母不合适，n-=Num，更换成字典序第二的字母，重复上述计算。如果一直是Num<n，则无解。

PS.zyy的数学不好，说得有点啰嗦，请各位大神不吝指教~

下面是我的实现：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 #define MaxLen 30
7 int T,N;
8 int Cnt[30],Lit;
9 char str[MaxLen+5],Ans[MaxLen+5];
10 bool flag;
11 inline int fac(int t)
12 {
13 if(t<=2) 14 return t; 15 int i,Ret=1; 16 for(i=2;i<=t;i++) 17 Ret*=i; 18 return Ret; 19 } 20 inline int Arg() 21 { 22 int i,Sum=0; 23 for(i=1;i<=26;i++) 24 { 25 if(!Cnt[i]) 26 continue; 27 Sum+=Cnt[i]; 28 } 29 Sum=fac(Sum); 30 for(i=1;i<=26;i++) 31 { 32 if(!Cnt[i]) 33 continue; 34 Sum/=fac(Cnt[i]); 35 } 36 return Sum; 37 } 38 void Work(int pos,int n) 39 { 40 int i,Num; 41 for(i=1;i<=26;) 42 { 43 if(!Cnt[i]) 44 { 45 i++; continue; 46 } 47 Cnt[i]--; 48 Num=Arg(); 49 if(Num==0) 50 { 51 Ans[pos]='a'+i-1; 52 return; 53 } 54 else if(Num=2)
100 {
101 printf("XXX\n");
102 continue;
103 }
104 flag=true;
105 Work(1,N);
106 if(!flag)
107 printf("XXX\n");
108 else
109 {
110 for(i=1;i<=Lit;i++) 111 printf("%c",Ans[i]); 112 if(Lit*2==Len) 113 for(i=Lit;i>=1;i--)
114 printf("%c",Ans[i]);
115 else
116 for(i=Lit-1;i>=1;i--)
117 printf("%c",Ans[i]);
118 printf("\n");
119 }
120 }
121 return 0;
122 }