黑客 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL MOD = 1000000007;
const int maxn = 500000 + 100;
int n, nn;
LL ans;
LL num[maxn];
LL cnt[maxn], fac[maxn], facInv[maxn];

LL fastPow(LL res, LL n) {
    LL ans;
    for (ans = 1; n != 0; n >>= 1) {
        if ((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}

LL inv(LL x) {
    return fastPow(x, MOD - 2);
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    facInv[maxn - 1] = inv(fac[maxn - 1]);
    for (int i = maxn - 2; i >= 0; --i) {
        facInv[i] = facInv[i + 1] * (i + 1) % MOD;
    }
}

LL solve(int x, int y) {
    if (cnt[x] < 1 || cnt[y] < 1) {
        return 0;
    }
    LL ret = fac[nn];
    --cnt[x];
    --cnt[y];
    for (int i = 0; i < n; ++i) {
        ret = ret * facInv[cnt[num[i]]] % MOD;
    }
    ++cnt[x];
    ++cnt[y];
    return ret;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc

    init();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        ++cnt[num[i]];
    }
    nn = n - 2;
    sort(num, num + n);
    n = unique(num, num + n) - num;
    for (int i = 1; i <= nn / i; ++i) {
        LL tmp = 0;
        if (nn % i == 0) {
            tmp = solve(i, nn / i) % MOD;
            if (nn / i != i) {
                tmp = tmp * 2 % MOD;
            }
        }
        ans = (ans + tmp) % MOD;
    }
    cout << ans << endl;

    return 0;
}