题解 | 小红的好排列

#include <iostream>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;  // 模数
const int N = 1000010;  // n的最大值加一些余量

LL fact[N], invfact[N];

// 快速幂计算a^b % p
LL powmod(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 初始化阶乘和逆元
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invfact[n] = powmod(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }
}

int main() {
    int n;
    cin >> n;   // 输入n
    init(n);    // 预计算阶乘和逆元

    int c0 = n / 3; // |S_0| = n / 3
    int k = n / 2 - c0; // 需要在T中分配k个V_0的值
    int m = n - c0; // |T| = n - c0

    // 边界检查，若k不合法，则无解
    if (k < 0 || k > m || k > c0) {
        cout << 0 << endl;
        return 0;
    }

    // 计算结果：(m!)^2 * (c0!)^2 / (k!)^2 / (m-k)! / (c0-k)!
    LL res = fact[m] * fact[m] % MOD;   // ((n - c0)!)^2
    res = res * fact[c0] % MOD * fact[c0] % MOD;    // * (c0!)^2
    res = res * invfact[k] % MOD * invfact[k] % MOD;  // / (k!)^2
    res = res * invfact[m - k] % MOD;         // / ((n-c0)-k)!
    res = res * invfact[c0 - k] % MOD;        // / (c0-k)!

    cout << res << endl;  // 输出结果
    return 0;
}
// 64 位输出请用 printf("%lld")