内网2082 字母

ACM
  1. 1.

##Description

乐乐开始学习英文字母了,小C为他准备了很多字母牌,每张牌有一个英文字母。有天乐乐把所有的牌排成一行,这些字母竟然形成了一个回文串。小C想知道,乐乐在排字母的时候,有多少种情况,最后的字母形成回文串。

##Input

输入一行,表示乐乐有哪些字母,均大写。

##Output

输出有多少种情况,排列的字母是一个回文串。

##Sample Input
AAAAB AABB CD

##Sample Output

1 2 0

##Hint
100%的数据,字母的个数不超过1000。


A(m,m)/(A(cnt1,cnt1)*A(cnt2,cnt2)…….)

主要是排列组合数的计算技巧。将n!分解质因数,然后上面的因子减去下面相同的因子,这样就不会因为计算阶乘而爆数组了。n!中质因数m的个数:n/m+n/m^2+n/m^3+n/m^4………

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "iostream"
#include "cstdio"
#include "cstring"
#include "string"
#include "vector"
using namespace std;
#define sz(x) (int)x.size()
#define DSIZE 10000
#define clr(x,y) memset(x,y,sizeof(x));
class BigInteger {
private:
    int a[1001];
    bool sign; //true-p , false-n
    int len;
public:
    BigInteger() {
        len = 1;
        sign = true;
        clr(a, 0);
        a[0] = 1;
    }
    void operator *=(int);
    friend ostream &operator<<(ostream &, const BigInteger &);
};
void BigInteger::operator*=(int x) {
    if (x < 0) x = -x, sign ^= 1;
    for (int i = 0; i < len; i++) {
        a[i] *= x;
    }
    for (int i = 0; i < len; i++) {
        if (a[i] >= DSIZE) {
            a[i + 1] += a[i] / DSIZE;
            a[i] %= DSIZE;
        }
    }
    if (a[len]) len++;
}
ostream &operator<<(ostream &out, const BigInteger &x) {
    if (!x.sign && x.len) putchar('-');
    printf("%d", x.a[x.len - 1]);
    for (int i = x.len - 2; i >= 0; i--) {
        printf("%04d", x.a[i]);
    }
    return out;
}
int n, m;
int cnt[30];
int prime[1001], tot;
bool ok[1001];
int faclist[1001];
void getprime(int n) {
    clr(ok, 0);
    tot = 0;
    for (int i = 2; i <= n; i++) {
        if (!ok[i]) prime[tot++] = i;
        for (int j = 0; j < tot; j++) {
            int now = i * prime[j];
            if (now > n) break;
            ok[now] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
void getfact(int x) {
    int s = x < 0 ? -x : x;
    for (int i = 0; prime[i] <= s; i++) {
        for (int j = prime[i]; j <= s; j *= prime[i]) {
            faclist[i] += x / j;
        }
    }
}
char str[1001];
int main() {
    getprime(1000);
    while (~scanf("%s",str)) {
        n = strlen(str);
        clr(cnt, 0);
        for (int i = 0; i < n; i++) {
            cnt[str[i] - 'A']++;
        }
        int f = 0;
        m = 0;
        for (int i = 0; i < 26 && f < 2; i++) {
            if (cnt[i] & 1) f++;
            m += cnt[i] >>= 1;
        }
        if (f > 1) {
            printf("0\n");
            continue;
        }
        clr(faclist, 0);
        getfact(m);
        for (int i = 0; i < 26; i++)
            getfact(-cnt[i]);
        BigInteger res;
        for (int i = 0; prime[i] <= m; i++) {
            for (int j = 0; j < faclist[i]; j++) {
                res *= prime[i];
            }
        }
        cout << res << endl;
    }
}
```language