题解 P5684 【非回文串】

· · 题解

很简单的数数入门题，比 CSP-S Day2 T1 良心多了（

注意到每个字符都是有标号的，所以非回文串数等于 n! 减去回文串数。
记第 i 种字母的出现次数为 a_i\ (i\in[1,26])，如果有超过 1 种 a_i 为奇数，则不可能组成回文串，答案为 n!。

为了下面表述方便，默认所有 a_i 都为偶数。

由于回文串是左右对称的，所以只考虑确定一边，另一边的每个字母都可以在对应位置随便排列（当然左右可以互换），也就是 a_i! 种。

所以对于左边的每一种排列，贡献就是每个 a_i! 之积。

那么现在只需要算出：每种元素有 a_i/2 个，且无标号的排列数，乘上面的贡献就可以了。

如果没有重复，排列数当然是 (n/2)!；现在有重复元素，要除去所有重复的排列，也就是

( n/2)!\prod\limits_{i=1}^{26}\frac{1}{(a_i/2)!}

不嫌麻烦也可以用 EGF 来推出这个结果，不用动脑子（

所以最终答案就是

n!-\left( (n/2)!\prod\limits_{i=1}^{26}\frac{a_i!}{(a_i/2)!}\right)

不过这是 a_i 全都是偶数的情况。
对于有一个是奇数的时候，设为 x；可以从 x 中选一个放在中间，所以右边那部分要再乘 x。

时间复杂度 \Theta(n)。

#include<cstdio> 
#include<algorithm>
#include<cstring>
#define ll long long
#define N 2003
#define reg register
#define p 1000000007
using namespace std;

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

int n,ans,dec,odd;
char a[N];
int fac[N],ifac[N],cnt[26];

int main(){
    scanf("%d",&n);
    scanf("%s",a+1);
    ifac[0] = ifac[1] = fac[0] = fac[1] = 1;
    for(reg int i=2;i<=n;++i) ifac[i] = fac[i] = (ll)fac[i-1]*i%p;
    ifac[n] = power(fac[n],p-2);
    for(reg int i=n-1;i>1;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
    for(reg int i=1;i<=n;++i) ++cnt[a[i]-'a'];
    for(reg int i=0;i<26;++i) odd += cnt[i]&1;
    if(odd>1){
        printf("%d",fac[n]);
        return 0;
    }
    odd = 1;
    for(reg int i=0;i<26;++i)
        if(cnt[i]&1) odd = cnt[i];
    dec = (ll)fac[n>>1]*odd%p;
    for(reg int i=0;i<26;++i) cnt[i] >>= 1;
    for(reg int i=0;i<26;++i) dec = (ll)dec*fac[cnt[i]<<1]%p*ifac[cnt[i]]%p;
    ans = (fac[n]-dec+p)%p;
    printf("%d",ans);
    return 0;
}