3 aa aabb a
1 2 1
题意： 有一串字符 可以随意交换每个字符的顺序 输出能组成的回文串的个数
注意的是 求排列组合的时候不能直接取模相除 会WA
首先统计每个字符出现的次数，然后在进行排列组合
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
ll extend_gcd(ll a,ll b,ll &x,ll &y)
{
if(a==0&&b==0) return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
ll d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
ll mod_reverse(ll a,ll n)
{
ll x,y;
ll d=extend_gcd(a,n,x,y);
if(d==1) return (x%n+n)%n;
else return -1;
}
ll c(ll m,ll n)
{
ll i,j,t1,t2,ans;
t1=t2=1;
for(i=n;i>=n-m+1;i--) t1=t1*i%mod;
for(i=1;i<=m;i++) t2=t2*i%mod;
return t1*mod_reverse(t2,mod)%mod;
}
int main()
{
int n;
char ch[1010];
int a[26];
scanf("%d",&n);
while(n--)
{
memset(a,0,sizeof(a));
scanf("%s",ch);
int len=strlen(ch);
for(int i=0;i<len;i++)a[ch[i]-'a']++;
int flag=0;
for(int i=0;i<26;i++)
if(a[i]&1) flag++;
if(flag>1) //出现两个奇数的字符则不可能组成回文串了 不需要判断字符串长度是否为奇偶
{
printf("0\n");
}
else
{
ll ans=1;
int sum=len/2;
for(int i=0;i<26;i++) //对每个字符进行位置的排列组合
{
if(a[i]&1) a[i]--;
ans=(ans*c(a[i]/2,sum))%mod;
sum-=a[i]/2;
}
printf("%lld\n",ans);
}
}
return 0;
}
HDU 5651 xiaoxin juju needs help
原文：http://blog.csdn.net/u013097262/article/details/51004943