题解 | 小红的好排列

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 计算 3 的倍数的个数
    int num_triples = n / 3;  // 1 到 n 中 3 的倍数的个数
    int num_half = n / 2;     // n 的一半，即需要满足条件的 i 的数量

    // 计算重叠部分的数量
    // 重叠部分是指同时满足 i 是 3 的倍数且 a_i 是 3 的倍数的情况
    int num_overlap = 2 * num_triples - num_half;

    // 初始化答案和模数
    long long ans = 1;
    long long mod = 1e9 + 7;

    // 计算组合数和排列数
    // 第一部分：从 num_triples 个 3 的倍数中选择 num_overlap 个
    for (int i = num_overlap + 1; i <= num_triples; i++) {
        ans = (ans * i) % mod;  // 计算 C(num_triples, num_overlap)
    }

    // 第二部分：从 num_triples 个 3 的倍数中选择 num_triples - num_overlap 个
    for (int i = num_triples - num_overlap + 1; i <= num_triples; i++) {
        ans = (ans * i) % mod;  // 计算 C(num_triples, num_triples - num_overlap)
    }

    // 第三部分：从 n - num_triples 个非 3 的倍数中选择 num_triples - num_overlap 个
    for (int i = num_triples - num_overlap + 1; i <= n - num_triples; i++) {
        ans = (ans * i) % mod;  // 计算 C(n - num_triples, num_triples - num_overlap)
    }

    // 第四部分：剩余的 n - 2 * num_triples + num_overlap 个位置可以任意排列
    for (int i = n - 2 * num_triples + num_overlap + 1; i <= n - num_triples; i++) {
        ans = (ans * i) % mod;  // 计算 (n - 2 * num_triples + num_overlap)! 的部分
    }

    // 输出最终结果
    cout << ans << endl;

    return 0;
}