P5684 [CSP-J2019 江西] 非回文串 题解

https://www.luogu.com.cn/problem/P5684

/*
比较简单的组合计数
题目没有以文字去描述，而是用下标来形式化题意，给我们一个关键信息：判定两个串是否相同不是看字符是否相同，而是看下标
换言之就是相同的字符，如果下标不同就算不同。这实际上更好算了进入正题：直接算非回文串很难，考虑正难则反，用总数n!减去回文串个数，就是非回文串个数
首先桶排，如果有>1种字符的数量为奇数，显然永远不可能排列成回文串（答案n!）
然后想想回文串个数怎么算：由于回文串的对称性考虑把回文串劈成两半，先确定一半里的字符，然后另一半的自然就对称过去了分情况讨论：（设t为桶数组）
1.所有字符个数都为偶数。直接按照上面的说法对称：(n/2)! * (t[1]!×t[2]!×...×t[26]!) / [(t[1]/2)!×(t[2]/2)!×...×(t[26]/2)!] = $\frac{\left(\frac{n}{2}\right)! \cdot \prod_{i = 1}^{26} t[i]!}{\prod_{i = 1}^{26} \left(\frac{t[i]}{2}\right)!}$组合意义：先确定左半边的排列(n/2)!，然后乘上变换下标顺序的方案数（为阶乘级别），但这样会多算因为(n/2)!已经考虑过左半边的顺序了，所以把这部分除掉，仅保留右边不同下标顺序的排列数
还有一种算法，先一个一个选左边哪些位置排什么字符（组合数），再乘上全排列的下标顺序方案数：=C(n/2,t[1]/2) * C(n/2-t[1]/2,t[2]/2) * C(n/2-t[1]/2-t[2]/2,t[3]/2) *...* (t[1]!×t[2]!×...×t[26]!)化简后是一样的2.只有一个字符个数为奇数，就把是奇数的那个排在最中间，然后两边对称排即可（就是在上面的情况下多乘一个选中间位置下标的方案数）：
坑点：如果有出现奇数个的，在最中间的那个已经固定，所以要少算一次！！！
设字符p出现奇数次，=(n/2)! * (t[1]!×t[2]!×...×(t[p]-1)!×...×t[26]!) / [(t[1]/2)!×(t[2]/2)!×...×((t[p]-1)/2)!×...×(t[26]/2)!] * t[p] = $(\frac{n}{2})! \times \frac{(t[1]! \times t[2]! \times \cdots \times (t[p]-1)! \times \cdots \times t[26]!)}{(\frac{t[1]}{2}!) \times (\frac{t[2]}{2}!) \times \cdots (\frac{t[p]-1}{2}!) \times \cdots \times (\frac{t[26]}{2}!)} \cdot t[p]$考虑预处理一个阶乘和阶乘逆元即可
*/#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2005, mod = 1e9 + 7;ll Pow(ll x, ll y){ll ans = 1;while(y){if(y & 1) ans=ans*x%mod;x=x*x%mod, y>>=1;}return ans;
}int n, t[26];
string s;
ll fac[maxn], ifac[maxn];void solve()
{cin >> n >> s;// 预处理fac[0] = 1;for(int i = 1; i <= n; i ++){fac[i] = fac[i - 1] * i % mod;}ifac[n] = Pow(fac[n], mod - 2);for(int i = n - 1; i >= 0; i --){ifac[i] = ifac[i + 1] * (i + 1) % mod;}// 桶排 + 特判for(char c : s) t[c-'a'] ++;bool flag = false; int p = -1; // 是否出现个数为奇数的字符、位置for(int i = 0; i < 26; i ++){if((t[i] & 1) && flag){ // 说明不止一个字符出现奇数次，不可能出现回文串，答案即为全排列cout << fac[n]; return ;}else if(t[i] & 1) flag = true, p = i;}// 算答案ll cnt = fac[n / 2]; // 非回文串个数for(int i = 0; i < 26; i ++){if(i == p){ // 特判cnt = cnt * fac[t[i] - 1] % mod * ifac[(t[i] - 1) / 2] % mod;}else{cnt = cnt * fac[t[i]] % mod * ifac[t[i] / 2] % mod;}}if(flag) cnt = cnt * t[p] % mod;ll ans = (fac[n] - cnt + mod) % mod; // 别忘了加mod防止负数cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}