题解 | 小红的好排列

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;

long long fact[MAX], inv_fact[MAX];

// 快速幂取模
long long pow_mod(long long x, int n) {
    long long res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

// 预处理阶乘和逆元
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[MAX-1] = pow_mod(fact[MAX-1], MOD-2);
    for (int i = MAX-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

// 组合数计算
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    precompute();
    int n;
    cin >> n;
    int k = n / 3;
    int s = n / 2 - k;
    int m = n - k;
    
    if (s < 0 || s > k || s > m) {
        cout << 0 << endl;
        return 0;
    }
    
    //从 m 个位置中选择 s 个位置，再从K个3的公倍数中选出S个，对K个数和n-k个数全排列
    long long c = comb(m, s);  
    long long perm1 = fact[k] * inv_fact[k - s] % MOD;  
    long long perm2 = fact[k] * inv_fact[s] % MOD;  
    long long ans = c * perm1 % MOD;
    ans = ans * perm2 % MOD;
    ans = ans * fact[n - k] % MOD;
    
    cout << ans << endl;
    return 0;
}