[CSP-J 2019 江西] 非回文串

知识点

组合计数、阶乘、乘法逆元、回文

解题思路

题目计算的是下标排列，故总数是n!，相同字符的位置仍不同。统计26种字符的次数c。若奇数次数的种类超过1，不能形成回文，答案即n!。否则先把每种字符的一半放入左半段，可得到(n/2)!/∏(c/2)!种回文字符串；每种字符串可以为每种字符安排c!种原下标，乘上∏c!即得到回文下标排列数。用总数减去此数，模质数计算。

正确性说明

回文的对称位置必须字符相同，所以至多一种字符次数为奇数。满足此条件时，中间字符唯一确定，左半段的多重集合排列与回文字符串一一对应。对固定字符串，某字符的c个不同原下标能以c!种方式安排到其位置，互相独立。故上述乘积恰好计入所有回文下标排列；从全部n!个排列中减去即为非回文数量。

易错点

样例aba的答案为4，不是不同非回文字符串的数量；模除法使用逆元；相减后加模数防负。

复杂度

预处理阶乘O(n+log MOD)，统计O(n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;long long pw(long long a,long long b){long long r=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)r=r*a%MOD;return r;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;int c[26]={};for(int i=0;i<n;i++){char x;cin>>x;++c[x-'a'];}vector<long long>f(n+1,1);for(int i=1;i<=n;i++)f[i]=f[i-1]*i%MOD;int odd=0;for(int x:c)odd+=x%2;if(odd>1){cout<<f[n]<<'\n';return 0;}long long pal=f[n/2];for(int x:c)pal=pal*pw(f[x/2],MOD-2)%MOD*f[x]%MOD;cout<<(f[n]-pal+MOD)%MOD<<'\n';}