HDOJ 5651-xiaoxin juju needs help【字符的全排列】

亦凉 2022-07-28 01:28 29阅读 0赞

# xiaoxin juju needs help #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1132 Accepted Submission(s): 324

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

This problem has multi test cases. First line contains a single integer  T(T≤20)![Image 1][] 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)![Image 1][].

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![Image 1][].

Sample Input

3
    aa
    aabb
    a

Sample Output

1
    2
    1

Source

[BestCoder Round \#77 (div.2) ][BestCoder Round _77 _div.2_]

解题思路：

我们要找到这个字符串可以组成多少个回文串，当然可以看出字母的个数为奇数的个数超过两个包括两个就输出0.

![Center][]

需要推出一个公式p表示字母数量/2.

#include <cstdio>
    #include <cstring>
    #define rep(i,j,k) for(i=j;i<k;++i)
    typedef long long ll;
    const ll mod = 1000000007;
    int p[26]; ll a[1001];
    char str[1005];
    ll quick_pow(ll a, ll b) {
        ll ans = 1;
        for (; b; b /= 2, a = (a * a) % mod)
            if (b & 1) ans = (ans * a) % mod;
        return ans;
    }
    int main() {
        int t, i, n, odd;
        a[0] = 1;
        rep(i,1,1001) a[i] = (a[i - 1] * i) % mod;
        scanf("%d", &t);
        while (t--) {
            memset(p, 0, sizeof p);
            scanf("%s", str);
            n = strlen(str); odd = -1;
            rep(i,0,n) ++p[str[i] - 'a'];
            ll ans = a[n / 2];
            rep(i,0,26) if (p[i] & 1)
                if (odd == -1) odd = i;
                else { ans = 0; goto end; }
            rep(i,0,26) ans = (ans * quick_pow(a[p[i] / 2], mod - 2)) % mod;
            end: printf("%lld\n", ans);
        }
        return 0;
    }

![Image 1][]

[Image 1]: 
[BestCoder Round _77 _div.2_]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2377+%28div.2%29&source=1&searchmode=source
[Center]: /images/20220727/90e28eebe01e414db6cbd0c67c5239c7.png