By yusijia

Updated:

Contents
  1. 1. hdu 5651
  2. 2. 题目：
  3. 3. 输入：
  4. 4. 输出：
  5. 5. 输入样例
  6. 6. 输出样例
  7. 7. 分析：

hdu 5651

题目：

“xiaoxin巨从小就喜欢字符串，六年级的时候他就知道了什么是回文串。这时，xiaoxin巨说到：如果一个字符串 SS 是回文串，那么该字符串从前往后看和从后往前看是一样一样的。

六年级的暑假，xiaoxin很快就做完了暑假作业，然后到腾讯做起了实习生。这日，leader给了xiaoxin一个字符串，请xiaoxin帮忙写一个函数来生成所有可能的回文串，可以任意改变字符串的顺序但是不可以扔掉某个字符。并且leader告诉xiaoxin，每生成一个不一样的回文串就可以得到一颗西瓜糖。

请你帮忙计算xiaoxin的leader最多需要买多少颗西瓜糖呢？

输入：

多组测试数据。第一行包含一个整数 T (T≤20) 表示组数。每组测试数据给出一个只包含小写字母的字符串 S(1≤length(S)≤1,000)

输出：

对于每组测试数据，输出一个数, 表示leader需要买的西瓜糖的个数，结果对 1,000,000,007 取模。

输入样例

3
aa
aabb
a

输出样例

1
2
1

分析：

  • 出现两个或两个以上不同的奇数个字母时结果为0,， 所以只需要考虑出现一个或全偶的情况。
  • 由于是回文，所以只需考虑一半的全排列，然后把重复的去掉，例如aaaabb，则可能出现重复 aab, 前两个a调换位置还是一样的。
  • N个元素的全排列总数为n！个，重点就是怎样把重复的去掉了，
  • n ! 通过除以元素出现次数的阶乘可以把重复的去掉，所以公式为：
    n！/ (n(a)/2)! / (n(b)2)!….

以aabb排列方式为例，前三位是aaa时排列为A33，但表现结果都是aabb，故每种3a2b的排列方式都包含了A33的3倍的方式，所以应除以A33
bb同理， 在以上基础上除以A22

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <cstdio>
#include <cstring>
#define MOD 1000000007

char s[1010];

int a[26], tt[1010];

inline int qpow(long long a, int n)  //快速幂
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return int(ans);
}

int main(int argc, char* argv[])
{
    int t;
    scanf("%d", &t);
    tt[0] = 1;
    for (int i = 1; i < 1010; ++i)      //预处理生成阶乘
        tt[i] = (long long)i * tt[i - 1] % MOD;
    while (t--)
    {
        long long ans = 0;
        int flag = 0;
        memset(a, 0, sizeof(a));
        scanf("%s", s);
        for (int i = 0; s[i] != '\0'; ++i)
            ++a[s[i] - 'a'];
        for (int i = 0; i < 26; ++i)
        {
            if (a[i] % 2 != 0)
            {
                if (++flag > 1)
                    break;		//如果出现两个或两个以上单数个字符个数就直接输出0
            }
            ans += a[i] >> 1;           //把每个字符出现的次数除以2，也就是考虑一半的情况

        }
        if (flag < 2)
        {
            ans = tt[ans];
            for (int i = 0; i < 26; ++i) if ((a[i]>>1) != 0)
                ans = ans * qpow(tt[a[i]>>1], MOD - 2) % MOD; //费马小定理
            printf("%d\n", int(ans));
        }
        else
            puts("0");                  //如果有两个或两个以上奇数个字母则结果为0
    }
    return 0;
}

//参考了师傅的博客：http://lioasdfghjkl.github.io/
Contents
  1. 1. hdu 5651
  2. 2. 题目：
  3. 3. 输入：
  4. 4. 输出：
  5. 5. 输入样例
  6. 6. 输出样例
  7. 7. 分析：