HDU 5651 xiaoxin juju needs help

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?

Input

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

1,000,000,007.

Sample Input

3
aa
aabb
a      

Sample Output

1
2
1      

今晚的BC又一次爆炸了，我忘記初始化結果終測死亡。。

這題就是統計一下字母個數，然而就是排列組合的問題了。

#include<cstdio>
#include<vector>
#include<queue>
#include<string>
#include<map>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int low(int x){ return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
int T, n, m;
int f[maxn], sum, c[maxn][maxn];
char s[maxn];

void init()
{
    c[0][0] = 1;
    for (int i = 1; i < maxn; i++)
    {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}

int main()
{
    init();
    scanf("%d", &T);
    while (T--)
    {
        for (int i = 0; i < 26; i++) f[i] = 0;
        scanf("%s", s);
        int cnt = sum = 0;
        LL ans = 0;
        for (int i = 0; s[i]; i++) f[s[i] - 'a']++;
        for (int i = 0; i < 26; i++)
        {
            if (f[i] & 1) cnt++, f[i]--;
            sum += f[i];
        }
        if (cnt <= 1)
        {
            ans = 1;    sum /= 2;
            for (int i = 0; i < 26; i++)
            {
                ans = (ans * c[sum][f[i] / 2]) % mod;
                sum -= f[i] / 2;
            }
        }
        cout << ans << endl;
    }
    return 0;
}