xiaoxin juju needs help
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 861 Accepted Submission(s): 243
Problem 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?
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).
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
Source
xiaoxin巨从小就喜欢字符串，六年级的时候他就知道了什么是回文串。这时，xiaoxin巨说到：如果一个字符串 S 是回文串，那么该字符串从前往后看和从后往前看是一样一样的。
六年级的暑假，xiaoxin很快就做完了暑假作业，然后到腾讯做起了实习生。这日，leader给了xiaoxin一个字符串，请xiaoxin帮忙写一个函数来生成所有可能的回文串，可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin，每生成一个不一样的回文串就可以得到一颗西瓜糖。
请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢？
解题思路：
回文字符串的个数可以根据一个公式来推导一下：
条件：
1.len = strlen(str),len>>=1;
2.num[i]：表示的是字符串每个字符 - 'a' 的个数，然后将其除以2；
结果： ret = (len!)/(num[0]! * num[1]! * ... * num[25]!) MOD 1e9+7;
根据这个公式我们只需要求一下阶乘的逆元就行了，因为是取模的运算，所以我们一边乘一边取模，不会超long long,最后不要忘记的是，如果是负数要转化为正数在进行取模，最后就是乘起来就行了。。。
My Code:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int MAXN = 1e3+5;
char str[MAXN];
int num[28];
LL a[28];
void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
LL x1, y1;
Ex_gcd(b, a%b, x1, y1);
x = y1;
y = x1-(a/b)*y1;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>str;
int len = strlen(str);
memset(num, 0, sizeof(num));
for(int i=0; i<len; i++)
num[str[i]-'a']++;
int sum = 0;
for(int i=0; i<26; i++)
if(num[i]%2)
sum++;
if(sum >= 2)
puts("0");
else
{
LL ret = 1;
len>>=1;
for(int i=0; i<26; i++)
{
LL x, y;
num[i]>>=1;
a[i] = 1;
for(int j=1; j<=num[i]; j++)
a[i] = a[i]*j%MOD;
Ex_gcd(a[i], MOD, x, y);
x = (x%MOD+MOD)%MOD;
a[i] = x;
}
for(int i=1; i<=len; i++)
ret = ret*i%MOD;
for(int i=0; i<26; i++)
ret = ret*a[i]%MOD;
printf("%lld\n",ret%MOD);
}
}
return 0;
}
