from math import factorial
from collections import Counter
s = input()
mp = Counter(s)
con_odd = 0
v = []
for num in mp.values():
    if num%2!=0:
        con_odd+=1
    else:
        v.append(num//2)

if con_odd>1:
    print(0)

res = factorial(sum(v))

for i in v:
    res//=factorial(i)

print(res)

from collections import Counter 
from math import perm, comb  

text = input()

# 使用Counter统计每个字符的出现次数，并将结果转换为字典
result = dict(Counter(text))
length = len(text)


jishu = 0

# 遍历每个字符及其出现次数
for key, value in result.items():
    # 如果出现次数是奇数，增加奇数计数器
    if value % 2 != 0:
        jishu += 1
    # 将出现次数减半（用于后续排列计算）
    result[key] = (value) // 2

# 如果奇数计数器大于1，无法形成回文，输出0
if jishu > 1:
    print(0)
else:
    # 计算总的排列数，初始为length//2的全排列
    result_num = perm(length // 2, length // 2)
    
    # 遍历每个字符及其减半后的出现次数，调整排列数
    for key, value in result.items():
        # 将排列数除以每个字符的排列数（value!）
        result_num = result_num // perm(value, value)
    print(result_num)

题面描述:

塔子哥最近迷上了一个字符串重排的游戏。游戏规则是给定一个由小写字母组成的字符串 ( s )，通过重新排列 ( s ) 中的字母，看看最多能组成多少个不同的回文字符串。如果无法组成任何回文字符串，则输出 ( 0 )。请编写一个程序来实现这个功能。输入格式为一行包含字符串 ( s )，输出格式为一个整数，表示可以组成的不同回文字符串的数量。例如，输入 "aabb" 时，输出应为 ( 2 )。

思路

如果存在两个以上的个数为奇数的字符显然不能构成回文。

对于其他为偶数的情况，因为是回文串，所以我们只需考虑其中半边的情况即可。

现在问题变成了，有 K 种字母，每个字母的个数为 $cnt_i$ 个，问有多少种情况

假设 K 种字母的和为 $n$

那么计算公式为：

对此我们只需预处理阶层即可 $O(1)$ 计算单个结果，由于涉及到大数运算，这里采用 python 来实现。

关键点分析

1. 回文字符串的特性：

   • 对于一个字符串能构成回文，最多只能有一个字符出现奇数次。因为在回文的中心可以放置这个字符，而其他字符必须成对出现。
   • 如果存在两个或以上的字符出现奇数次，则无法构成回文串，直接输出 ( 0 )。

2. 字符计数：

   • 统计字符串中每个字符的出现次数，分为奇数和偶数。
   • 只需要考虑每个字符的一半的数量来计算不同的回文串，因为回文的前半部分决定了整个回文。

3. 排列计算：

   • 计算回文的一半所需的字符的排列方式。假设我们有 ( K ) 种字符，每种字符的数量为 ( cnt_i )，我们需要计算总的排列数。
   • 总的排列数为所有字符的一半的总数的阶乘，然后除以每种字符的一半的数量的阶乘，以避免重复排列。

解决方案步骤

1. 统计字符频率：使用哈希表统计每个字符的出现次数。
2. 判断奇数字符的数量：遍历统计结果，记录出现奇数次的字符数量。
   • 如果奇数字符的数量大于 1，则输出 ( 0 )。
3. 计算字符的半数：将每个字符的计数除以 2，存储这些值。
4. 预处理阶乘：计算并存储从 ( 0 ) 到 ( n ) 的阶乘，以便后续快速计算。
5. 计算回文串的数量：根据公式计算可能的排列数，输出结果。

AC代码

Python

from collections import Counter


s = input().strip()
mp = Counter(s)  # 统计字符串中各个字符的个数
cnt = 0
v = []

# 统计奇数字符个数和偶数字符个数
for value in mp.values():
    if value % 2 == 1:
        cnt += 1
    v.append(value // 2)

# 如果奇数字符个数大于1，则无法构成回文串
if cnt > 1:
    print(0)
    exit(0)

# 计算回文串数量
total = sum(v)  # 总的字符数量的一半
f = [1] * (total + 1)  # 预处理阶乘值
for i in range(1, total + 1):
    f[i] = f[i - 1] * i

res = f[total]  # 计算全部字符的排列数
for i in v:
    res //= f[i]  # 除去各个字符的排列数

print(res)

java

import java.math.BigInteger;
import java.util.*;

public class Main {
    private static BigInteger palindromeNum(String str) {
        // 将字符串转换为字符数组
        char[] s = str.toCharArray();
        // 创建一个长度为26的数组，存储每个字母出现的次数
        int[] map = new int[26];
        for (char c : s) {
            map[c - 'a']++;
        }
        // 判断是否有超过一个的奇数字符
        boolean odd = false;
        for (int i = 0; i < 26; i++) {
            if (map[i] % 2 == 1) {
                if (odd) {
                    // 如果有超过一个奇数字符，则无法构成回文串，返回0
                    return new BigInteger("0");
                } else {
                    odd = true;
                }
            }
            // 将每个字母的个数除以2，因为回文串中每个字母出现的次数必须是偶数
            map[i] /= 2;
        }
        // 计算回文串的数量
        int n = s.length / 2;
        // 预先计算阶乘值，以便后续使用
        BigInteger[] f = new BigInteger[n + 1];
        f[0] = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1].multiply(new BigInteger(String.valueOf(i)));
        }
        // 除去每种字符的排列数
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) {
                f[n] = f[n].divide(f[map[i]]);
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        System.out.println(palindromeNum(s));
    }
}

C++

塔子哥的tips:这题确实对C++不公平。同样的思路却需要自己实现大整数，而其他语言都有对大整数模拟的封装。但是也没办法，因为C++实现大整数需要100+行代码。如果真的追求完美，C++这题起码写200行。所以碰到这种出题人，只能认栽。写个正常的算法看看能过多少就算了。赶快去其他题拿分。

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    // 统计字符串中各个字符的个数
    unordered_map<char, int> mp;
    for (char c : s) {
        mp[c]++;
    }

    int cnt = 0;
    vector<int> v;

    // 统计奇数字符个数和偶数字符个数
    for (auto [_, value] : mp) {
        if (value % 2 == 1) {
            cnt++;
        }
        v.push_back(value / 2);
    }

    // 如果奇数字符个数大于1，则无法构成回文串
    if (cnt > 1) {
        cout << 0 << endl;
        return 0;
    }

    // 计算回文串数量
    int total = 0;
    for (int x : v) {
        total += x;
    }

    vector<long long> f(total + 1, 1);  // 预处理阶乘值
    for (int i = 1; i <= total; i++) {
        f[i] = f[i - 1] * i;
    }

    long long res = f[total];  // 计算全部字符的排列数
    for (int x : v) {
        res /= f[x];  // 除去各个字符的排列数
    }

    cout << res << endl;
    return 0;
}