自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:13:22，当前版本为作者最后更新于2019-11-24 10:30:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很简单的数数入门题，比 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;
}