非回文串[洛谷P5684][CSP-J2019 江西]

[原题传送门](https://www.luogu.com.cn/problem/P5684 "原题传送门")
### 题意
Alice 有 n
 个字符，它们都是英文小写字母，从 1∼n
 编号，分别为 c1,c2,⋯,cn
 。
Bob 准备将这些字符重新排列，组成一个字符串 S。Bob 知道 Alice 有强迫症，所以他打算将 S 组成一个非回文串来折磨 Alice。

现在 Bob 想知道他共有多少种不同的排列字符的方案，能使得 S 是个非回文串。一种排列字符的方案指的是一个 1∼n 的排列 pi ，它所组成的 S=cp1cp2⋯cpn 。

一个字符串是非回文串，当且仅当它的逆序串与原串不同。例如 abcda 的逆序串为 adcba
，与原串不同，故 abcda 是非回文串。而 abcba 的逆序串与原串相同，是回文串。

由于最后的结果可能很大，你只需要告诉 Bob 总方案数对 10^9+7 取模后的值。

### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
const int maxn = 2020;
long long f[maxn];
int n, cnt[26];
string s;

typedef long long ll;
void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
    if(!b) {d = a; x = 1; y = 0;}
    else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n) {
    ll d , x , y;
    gcd(a , n , d,  x , y);
    return d == 1 ? (x+n)%n : -1;
}

void init() {
    f[0] = 1;
    for (int i = 1; i < maxn; i ++) f[i] = f[i-1] * i % MOD;
}
int main() {
    init();
    cin >> n >> s;
    for (int i = 0; i < n; i ++) cnt[s[i] - 'a'] ++;
    int cc = 0;
    for (int i = 0; i < 26; i ++) if (cnt[i]%2) cc ++;
    if (cc > 1) cout << f[n] << endl;
    else {
        long long res = f[n/2];
        for (int i = 0; i < 26; i ++) {
            res = res * f[cnt[i]] % MOD;
            res = res * inv(f[cnt[i]/2], MOD) % MOD;
        }
        res = (f[n] - res + MOD) % MOD;
        cout << res << endl;
    }
    return 0;
}
```