xiaoxin juju needs help
题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5651
Description
As we all known, xiaoxin is a brilliant coder. He knew palindromic strings when he was only a six grade student at elementry school.
This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin’s leader needs to buy?
Input
This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, there is a single line containing a string S(1≤length(S)≤1,000).
Output
For each test case, print an integer which is the number of watermelon candies xiaoxin’s leader needs to buy after mod 1,000,000,007.
Sample Input
3
aa
aabb
a
Sample Output
1
2
1
Hint
题意
给你一个串，你可以改变字符位置
问你能够形成多少种回文串。
题解：
首先把答案为0的情况判断掉
然后就很简单了，因为回文嘛，所以左右肯定相同
然后就可以排列组合怼一波了
就相当于选位置，把所有字母安上去。
C(x1,x2)*C(y1,y2)….这种
代码
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e5+7;
int num[30];
typedef long long ll;
ll fac[maxn];
ll qpow(ll a,ll b)
{
ll ans=1;a%=mod;
for(ll i=b;i;i>>=1,a=a*a%mod)
if(i&1)ans=ans*a%mod;
return ans;
}
ll C(ll n,ll m)
{
if(m>n||m<0)return 0;
ll s1=fac[n],s2=fac[n-m]*fac[m]%mod;
return s1*qpow(s2,mod-2)%mod;
}
void solve()
{
memset(num,0,sizeof(num));
string s;cin>>s;
for(int i=0;i<s.size();i++)
num[s[i]-'a']++;
if(s.size()%2==0)
{
for(int i=0;i<26;i++)
if(num[i]%2==1)
{
printf("0\n");
return;
}
}
else
{
int cnt = 0;
for(int i=0;i<26;i++)
if(num[i]%2==1)cnt++;
if(cnt!=1)
{
printf("0\n");
return;
}
}
long long ans = 1;
long long las = s.size();
for(int i=0;i<26;i++)
{
ans = (ans * C(las/2,num[i]/2))%mod;
las-=num[i];
}
printf("%lld\n",ans);
}
int main()
{
fac[0]=1;
for(int i=1;i<maxn;i++)
fac[i]=fac[i-1]*i%mod;
int t;scanf("%d",&t);
while(t--)solve();
return 0;
}发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109105.html原文链接：https://javaforall.net
