阶乘逆元+排列数

解题思路:阶乘逆元+排列数
注意事项:用long long，每乘一个数就取模，避免溢出。

参考代码:

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll pow(ll a, int b, int mod) {

    ll res = 1;

    while (b) {

        if (b & 1) res = res * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return res;

}

int counts[500001]{};

ll inv_fac[500001]{};

ll fac[500001]{};

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    const int mod = 1e9 + 7;

    int n;

    cin >> n;

    int nums[n];

    for (int i = 0; i < n; i++) {

        int x;

        cin >> x;

        counts[x]++;

        nums[i] = x;

    }

    n -= 2;

    fac[0] = 1;

    for (int i = 1; i <= 500000; i++) fac[i] = fac[i - 1] * i % mod;

    inv_fac[500000] = pow(fac[500000], mod - 2, mod);

    for (int i = 499999; i >= 0; i--) inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;

    ll a = fac[n];

    for (int x:counts) if (x >= 2) a = a * inv_fac[x] % mod;

    ll ans = 0;

    for (int i = 1; i * i <= n; i++) {

        if (n % i != 0 || counts[i] == 0) continue;

        int j = n / i;

        if (counts[j] == 0 || i == j && counts[j] < 2) continue;

        if (i == j) ans = (ans + a * fac[counts[i]] % mod * inv_fac[counts[i] - 2] % mod) % mod;

        else

            ans = (ans + a * fac[counts[i]] % mod * fac[counts[j]] % mod * inv_fac[counts[i] - 1] % mod *

                         inv_fac[counts[j] - 1] % mod * 2 % mod) % mod;

    }

    cout << ans << endl;

    return 0;

}