数学题（字符串的解码与编码，涉及组合数学）
题意：给你一个字符串，它们的全排列中有一些字符将会是回文串，单独把这个些回文串拿出来，按字典序给他们从1开始编号。然后输入数字n，把第n个回文串输出。
这题第一次看完全不会放下几天，今天再看瞬间想通。首先这题要从回文串的性质分析：一个回文串如果长度为偶数，那么可以确定，每种字符的个数一个是偶数，不会有字符的个数为奇数。如果一个回文串为奇数，那么可以确定，一定有且仅有一种字符的个数为奇数，其他字符的个数都会偶数，而且整个回文串中间的那个字符必定是为奇数的那个字符。所以对于长度为奇数的回文串，我们可以暂时除掉中间的那个字符（因为它是固定一定要在那里，没什么研究价值），把它变为一个长度为偶数的回文串（但是记得最终输出的时候把除掉的那个字符补上）。我们来看长度为偶数的回文串，两两对称，所有我们只需要研究左半部分，右半部分只是复制罢了，也就是说，一个回文串最终长什么样，是由左半部分决定的。
所以我们只对左半部分按照字典序排序，那么左半部分的排序结果也会是整个回文串的排序结果
有人不禁要质疑上面的这条结论，说是会不会左半部分的排序和整个回文串的排序不同，这是不可能的，因为字典序的比较是第一次遇到不同就停止。
所以我们要找第n个回文串，实际就是找左半字符串全排列中的第n个排列，这是一个解码的过程，就是一位一位地确定字符
我们用例子来说明问题：
假设经过处理后我们的到的左半部分字符串是ababcdac，我们要知道第698个排列的字符串
3个a，2个b，2个c，1个d，总长度为8
我们从第一位开始确定，第一位可以是a，b，c，d
第一位为a，剩下2个a，2个b，2个c，1个d，他们的全排列个数要用组合数学来算为 (2+2+2+1)! / (2!2!2!1!)=630
而698>630，所以第1位不能填a , 698-630=68
第一位为b，剩下3个a，1个b，2个c，1个d，全排序个数为(3+1+2+1)! / (3!1!2!1!)=420
而68<420 , 说明第一位填b
——————————————————————————
68 , 3个a，1个b，2个c，1个d，总长度为7
若第二位填a，剩下2个a，1个b，2个c，1个d，全排列数为 6！/ 2!1!2!1! = 180 , 68<180 ， 说明第2位填a
——————————————————————————
68 ， 2个a，1个b，2个c，1个d ， 总长度为6
若第3位填a，剩下1个a，1个b，2个c，1个d， 全排列数为 5！/ 1!1!2!1! = 60 , 68>60 , 不能填a ， 68-60=8
若第3位填b，剩下2个a，2个c，1个d，全排列为 5！/ 2!2!1! = 30 , 8<30 , 说明第3位填b
———————————————————————————
8 ， 2个a，2个c，1个d ， 总长度为5
若第4位填a，剩下1个a，2个c，1个d ， 全排列个数为 4！/ 1!2!1! = 12 , 若8<12 , 说明第4位填a
———————————————————————————
8，1个a，2个c，1个d ， 总长度为4
若第5位填a，剩下2个c，1个d，全排列数为 3！/ 2!1!=3 , 8>3 , 不能填a，8-3=5
若第5位填c，剩下1个a，1个c，1个d，全排列为 3! / 1!1!1! = 6 , 5<6 ， 说明第5位填c
————————————————————————————
5 , 1个a，1个c，1个d , 总长度为3
若第6位为a ， 剩下 1个c，1个d ， 全排列为 2 , 5>2 , 不能填a ， 5-2=3
若第6位为c， 剩下1个a，1个d， 全排列为 2 ， 3>2 , 不能填c ， 3-2=1
若第6位为d， 剩下1个a，1个c，全排列为2 ， 1<2 , 说明第6位为d
—————————————————————————————
1 ， 1个a，1个c ， 总长度为2
若第7位为a ， 剩下1个c， 全排列数为 1 ， 1<=1 , 说明第7位填a
——————————————————————————————
1 ， 1个c ， 第8位填c
——————————————————————————————
最终得到字符串为 babacdac
上面的迭代过程用代码实现即可，不过注意一个陷阱，输入中的字符串可能本身根本无法构成回文（超过一种字符的个数为奇数）
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long num; int LEN; int c[30]; char ans[30],mid; long long P(int n) { long long ans=1; while(n) { ans*=n; n--;} return ans; } void solve() { long long a=1,b=1; a=P(LEN); for(int i=0; i<26; i++) if(c[i]) b*=P(c[i]); if(num>a/b) { printf("XXX\n"); return ;} //超出总排列数 int i,j,cur=1; memset(ans,0,sizeof(ans)); while(cur<=LEN) { for(i=0; i<26; i++) if(c[i])//枚举当前位能填的字母 { c[i]--; //暂时减1，到时候看情况加回来 a=P(LEN-cur); //分子 for(b=1,j=0; j<26; j++) if(c[j]) b*=P(c[j]); //分母 long long m=a/b; //填i这个字母的排列数 if(num>m) { num-=m; c[i]++; } //填i不够，需要枚举下一个 else { ans[cur]=i; break; } //当天位填i } cur++; } for(i=1; i<=LEN; i++) printf("%c",ans[i]+'a'); if(mid) printf("%c",mid); for(i=LEN; i>=1; i--) printf("%c",ans[i]+'a'); printf("\n"); } bool init() { int i,ccount; char s[50]; scanf("%s%lld",s,&num); LEN=strlen(s); memset(c,0,sizeof(c)); for(int i=0; i<LEN; i++) c[s[i]-'a']++; for(mid='\0' , ccount=0 , i=0; i<26; i++) { if(c[i]&1) //扫描26个字母,找出个数为奇数的作为中间值 { mid=i+'a'; ccount++; } //统计多少个字符的个数为奇数 c[i]=c[i]>>1; //个数都减半，因为我们只要一半去构建左半部分 } LEN=LEN>>1; //总长度也折半 if(ccount>1) return 0; //原字符串不可能构成回文 else return 1; } int main() { int Case,T; scanf("%d",&T); for(Case=1; Case<=T; Case++) { bool a=init(); printf("Case %d: ",Case); if(!a) printf("XXX\n"); //原字符串本身不能构成回文 else solve(); } return 0; }
最后复习一下。有m种小球，每种小球的个数分别为n1，n2，n3……nm，总的排列总数为
(n1+n2+n3……nm)! / (n1!n2!n3!……nm!)