HDU 5651 xiaoxin juju needs help：排列組合計算回文串個數

題目背景

給定一個字符串，可以任意重新排列字符順序。求能組成多少個不同的回文串，答案對 1,000,000,007 取模。

解題關鍵

1. 回文構成條件：最多只能有一個字符出現奇數次。若有兩個以上奇數字符，答案直接為 0。
2. 排列計數：將每個字符出現次數減半（奇數字符保留一個作為中心），問題轉化為求多重集合的排列數：

   總方案數 = (Σ cnt[i]/2)! / Π (cnt[i]/2)!
   

3. 模逆元處理：分母不能直接取模除，需用擴展歐幾里得算法求模逆元，或預處理階乘與逆元。

核心代碼片段（C++）

const int MOD = 1e9 + 7;
typedef long long ll;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll d = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll mod_inv(ll a, ll n) {
    ll x, y;
    ll d = ext_gcd(a, n, x, y);
    return d == 1 ? (x % n + n) % n : -1;
}

ll C(int m, int n) { // 計算 C(n, m)
    if (m < 0 || m > n) return 0;
    ll num = 1, den = 1;
    for (int i = 0; i < m; ++i) num = num * (n - i) % MOD;
    for (int i = 1; i <= m; ++i) den = den * i % MOD;
    return num * mod_inv(den, MOD) % MOD;
}

int main() {
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int cnt[26] = {0};
        for (char ch : s) cnt[ch - 'a']++;
        int odd = 0;
        for (int i = 0; i < 26; ++i) if (cnt[i] & 1) odd++;
        if (odd > 1) { cout << 0 << '\n'; continue; }
        ll ans = 1;
        int half = s.size() / 2;
        for (int i = 0; i < 26; ++i) {
            int use = cnt[i] / 2;
            ans = ans * C(use, half) % MOD;
            half -= use;
        }
        cout << ans << '\n';
    }
}

注意事項

• 組合數計算時分子分母同步取模，最後乘以分母的模逆元。
• 字符串長度 ≤ 1000，預處理階乘至 500 即可進一步優化。