非回文串

byxiaofu · 2023-03-07 13:25:00 · 题解

思路

这是一道数学题，既然非回文串不好求，那可以用总方案数减去回文串的数量，回文串是有一些好的性质的，正着读反着读都一样，也就是对称性，利用这个性质，做出以下推导：

总排列方案为：n!，实质就是全排列。 回文串左半边的排列方案数：\frac{n}{2}! ，同上。 根据排列组合，把 \frac{n}{2} 个字符放在 n 个位置里，也就是相当于把一些元素的一半放在这些元素数量的位置上，显然这是排列，然后总共二十六个字母，都要有组合。得到非回文串的总排列方式为（因为这个是无序的，所以用排列）：

注意事项&常见错误原因

• WA on #2，#8，请注意你的公式是不是写错了。
• 大红大紫，请注意你的模数是不是没有初始化，另外看看数组为了节省而开小了一个。
• WA on #3，#5，#6，#7，#9，这个没有别的方法，只能把公式分开写，放在一起会导致溢出。

• 对于逆元的解决，只需在纸上写一下，就能发现可以约分，还是一个连乘，具体见代码。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  const int mod=1e9+7;
  int s[26];
  int fac(int n){
  long long cnt=1;
  for(int i=1;i<=n;i++)cnt=(cnt*i)%mod;
  return cnt;
  }
  int fact(int n){
  long long cnt=1;
  for(int i=n/2+1;i<=n;i++)cnt=(cnt*i)%mod;
  return cnt;
  }
  signed main(){
  int n;cin>>n;
  for(int i=1;i<=n;i++){
      char x;cin>>x;
      s[x-'a']++;
  }
  int cnt=0,ans=fac(n);
  for(int i=0;i<26;i++)if(s[i]%2==1)cnt++;
  if(cnt>1){
      cout<<ans;return 0;}
  else{
      long long cnt2=1;
      for(int i=0;i<26;i++)cnt2=(cnt2*fact(s[i]))%mod;
      cnt2=cnt2*fac(n/2)%mod;
      cout<<(ans-cnt2+mod)%mod;
  
  }
  return 0; 
  }