#include<bits/stdc++.h>
using namespace std;
int read() {
register int x=1,ans=0;register char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') x*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
return x*ans;
}
const long long N=2005,MOD=1e9+7;
long long s[30],n,sum,ans;
long long js(int a) {
long long res=1;
for(register long long i=1;i<=a;++i) {
res*=i; res%=MOD;
}
return res;
}
long long find(int x) {
long long res=1;
for(register long long i=1;x-i>0;i+=2) {
res*=i*2; res%=MOD;
}
if(x%2) res=res*x%MOD;
return res;
}
int main() {
n=read();
sum=js(n);
string a;
cin>>a;
for(register int i=0;i<n;++i) {
s[a[i]-'a']++;
}
long long k=0;
for(register int i=0;i<26;++i) {
if(s[i]%2) ++k;
}
if(k>1) {printf("%lldn",sum); return 0;}
ans=1; k=0;
for(register int i=0;i<26;++i) {
ans*=find(s[i]); ans%=MOD; k+=s[i]/2;
}
k=js(k);ans=(ans*k)%MOD;
ans=sum-ans;if(ans<0) ans+=MOD;
printf("%lldn",ans);
return 0;
}
题解 P5684 【[CSPJX2019]非回文串【民间数据】】
2020-01-27 00:00:00 题解
楼下的题解写的很好，如果作为一个提高组选手下面的题解不难懂的，但是给普及组的人来看的话还是比较难理解，这里我写一篇好理解的题解。
我认为一个好的题解不是把自己的思路转化为抽象的式子让后让别人去理解这个式子，而应该直接把自己的思路用语言图像告诉别人。
我们重新理解一下这个题目，你有26种字符，第i种字符有$S[i]$个，让你用这些字符组成对称的字符串，问你有多少种可能。
然鹅题目要你求的是非回文串的个数，所以你只需要用$n$个字符能组成的字符串的总个数$sum$减去这些字符能组成的回文串个数$ans$就是答案
我们先来求一下$sum$，可以这样理解，你有$n$个位置$n$个人，问有多少种不同的做法，先考虑第一个位置，这时有$n$个人，则有n总可能，考虑第二个位置，这时还剩$n-1$个人，有$n-1$种可能，所以这时的方案数为$sum=n*(n-1)$，考虑到最后一个位置的时候只有一个人了，也就是一种可能，所以总方案数为$sum=n*(n-1)*(n-2)*...*1$。也就是$sum$的阶乘$sum!$，下面我的代码里为js函数
然后我们考虑回文的情况也就是当n为偶数时，我们只考虑左边一半，此时右边一定有一个与之对应的字符。所以我们先考虑把这些字符两两配对起来看看有多少种情况，这个像上面js函数一样自己手推一下把，这在下面我的我的代码里为find函数
然后我们在看看这些配对好的字符可以组成多少种组合，也就是考虑n/2个字符可以组成多少种可能，此时每一种可能都有右边与之配对好了的字符形成回文。
最后还有一个当n为奇数时的情况，这是我们可以看到一定有一种字符是会落单的，我们只要枚举哪一个字符放中间然后按照n为奇数来计算就好了。
ps：我想吐槽一下今年的入门组题目忒简单了点，没人AK说不过去（可是没有人AK），所以拿JXpj省一的小伙子们不要太狂啊，你们接触到的都是很简单的题。
我们的目标是noi！！！JX要加油！
下面上代码
下一篇：关于下载钉钉直播回放
