内网2082 字母

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.........

#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

Comments