题目：http://acm.hdu.edu.cn/showproblem.php?pid=5651
xiaoxin巨从小就喜欢字符串，六年级的时候他就知道了什么是回文串。这时，xiaoxin巨说到：如果一个字符串 SS 是回文串，那么该字符串从前往后看和从后往前看是一样一样的。
六年级的暑假，xiaoxin很快就做完了暑假作业，然后到腾讯做起了实习生。这日，leader给了xiaoxin一个字符串，请xiaoxin帮忙写一个函数来生成所有可能的回文串，可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin，每生成一个不一样的回文串就可以得到一颗西瓜糖。
请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢？
输入描述
多组测试数据。第一行包含一个整数 T(T≤20) 表示组数。每组测试数据给出一个只包含小写字母的字符串 S(1≤length(S)≤1,000)
输出描述
对于每组测试数据，输出一个数, 表示leader需要买的西瓜糖的个数，结果对 1,000,000,007取模。
输入样例
3
aa
aabb
a
输出样例
1
2
1
题解：首先，如果不止一个字符出现的次数为奇数，则结果为0。 否则，我们把每个字符出现次数除2，也就是考虑一半的情况。 那么结果就是这个可重复集合的排列数了。 设该集合有n个数，第i个数出现次数为ai，那么结果就是 fact(n)/fact(a1)/fact(a2)/…./fact(an)。
分析：昨晚做的BC，太失败了，就这一题，很快就推出公式了，跟题解一模一样！但是因为这个阶乘吧，不好搞，自己很快敲了一个代码，交了一下WA（意料之中）。因为我知道除法取余操作那块会出错，但是我不知道怎么解决啊。于是又想去推别的公式，但是每个想的角度一般是固定的，我想的就是先全排列，再把重复的排列一个个除去。虽然我知道肯定还有别的排列方法，但是怎么想也想不出别的了。于是重新去解决阶乘除法的问题，我知道最后分母，肯定会被分子n!约去，就想着先把分母全部约去，再相乘，这样就可以了。于是就敲，样例都对，就是过不了，当时看着200多个人都A了，又开始怀疑自己的公式是不是错了？于是又开始找公式，到最后实在没心情做了，放弃了。。。。
做完后，掉了很多分，打击太大了，感觉到很迷茫啊！而后看题解，思路是一样的，难道我约分的地方错了？然后搜题解，有个人跟我想的一模一样！！！看我他的，我知道了，我约分是找完最小公倍数后相除。但是我不是用的队列，而是循环继续去找，这样就会导致有的分母会约不掉。。。
以上就是全过程，主要原因还是我心态的问题，还以自己公式推错了（现在想想，怎么会错呢！！）然后就是自己代码能力太弱，没想到用队列啊！还有就是自己见识太短了，这种阶乘除法的题目正解是用阶乘逆元去做，而自己根本就没见过。还有就是思考问题的角度，还有一个很简单的公式，但是每个人思考的角度是不同的自己没想出来也难怪。
法一：
fact(n)/fact(a1)/fact(a2)/…./fact(an)。先分母全部约掉。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=505;
const int mod=1e9+7;
char s[1001];
int cnt[26],b[505];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main()
{
//freopen("f.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);
int len=strlen(s);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<len;i++)cnt[s[i]-'a']++;
int tot=0;
for(int i=0;i<26;i++){
if(cnt[i]&1)tot++;
cnt[i]>>=1;
}
if(tot>1){printf("0
");continue;}
queue<int>q;
for(int i=0;i<26;i++){
if(cnt[i]){
for(int j=2;j<=cnt[i];j++)q.push(j);
}
}
int n=len/2;
for(int i=1;i<=n;i++)b[i]=i;
while(!q.empty()){
int t=q.front();q.pop();
for(int i=2;i<=n;i++){
if(b[i]%t==0){
b[i]/=t;break;
}
int y=gcd(b[i],t);
if(y>1){
b[i]/=y;
t/=y;
if(t>1)q.push(t);
break;
}
}
}
int ans=1;
for(int i=1;i<=n;i++){
ans=(ll)ans*b[i]%mod;
}
printf("%d
",ans);
}
return 0;
}
法二：
每次从剩余的位置中选择需要的字母个数，自己需要的就是这个想法啊！
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=505;
int n;
char s[N];
int a[27];
ll f[N][N];
void init()
{
for(int i=0;i<N;i++){
f[i][0]=1;
for(int j=1;j<=i;j++)f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);
int n=strlen(s);
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[s[i]-'a']++;
}
int cnt=0;
for(int i=0;i<26;i++){
if(a[i]&1)cnt++,a[i]--;
}
if(cnt>1){
printf("0
");continue;
}
int m=n/2;
ll ans=1;
for(int i=0;i<26;i++){
ans=ans*f[m][a[i]>>1]%mod;
m-=(a[i]>>1);
}
printf("%d
",(int)(ans));
}
return 0;
}法三：
逆元：a^(p-1) = 1(mod p)p为素数 于是 a*a^(p-2) = 1(mod p)所以a^(p-2)替代1/a.
看到还有人的代码两行递推就可以，先放放，以后再看看（这几天太忙了）
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=505;
char s[N];
int a[27];
int f[N];
int fpow(int a,int p)
{
int res=1;
for(;p;p>>=1){
if(p&1)res=(ll)res*a%mod;
a=(ll)a*a%mod;
}
return res;
}
int main()
{
f[1]=1;for(int i=2;i<N;i++)f[i]=(ll)f[i-1]*i%mod;
int T;scanf("%d",&T);
while(T--){
scanf("%s",s);
int n=strlen(s);
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[s[i]-'a']++;
}
int cnt=0;
for(int i=0;i<26;i++){
if(a[i]&1)cnt++;
a[i]>>=1;
}
if(cnt>1){
printf("0
");continue;
}
int m=n/2;
int ans=f[m];
for(int i=0;i<26;i++){
if(a[i])ans=(ll)ans*fpow(f[a[i]],mod-2)%mod;
}
printf("%d
",(int)(ans));
}
return 0;
}法四：
还有种最暴力，把所有的阶乘乘起来，最后再取模就好呗！（我咋没想到呢QAQ）
另外，想到了也不一定敲得出来，自己JAVA还学得有点水啊
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
static public void main(String[] args){
BigInteger []fac=new BigInteger[505];
fac[0]=new BigInteger("0");
fac[1]=new BigInteger("1");
for(int i=2;i<505;i++){
fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));
}
BigInteger mod=new BigInteger("1000000007");
Scanner in=new Scanner(System.in);
int []cnt=new int[26];
int n;
n=in.nextInt();
while(n--!=0){
String str;
str=in.next();
for(int i=0;i<26;i++)cnt[i]=0;
for(int i=0;i<str.length();i++){
cnt[str.charAt(i)-'a']++;
}
int flag=0;
for(int i=0;i<26;i++){
if((cnt[i]&1)==1)flag++;
cnt[i]>>=1;
}
if(flag>1){
System.out.println("0");
continue;
}
if(str.length()==1){
System.out.println("1");continue;
}
BigInteger ans=fac[str.length()/2];
BigInteger sum=new BigInteger("1");
for(int i=0;i<26;i++){
if(cnt[i]!=0){
sum=sum.multiply(fac[cnt[i]]);
}
}
System.out.println(ans.divide(sum).mod(mod));
}
}
}