题解 | 小红的好排列

本质数学题

我们可以求出这个这个排列里面有x = n//3个3的倍数，我们需要y = n//2个3的倍数

那么我们可以在x中选y - x个挪到外面，在外面n - x 个里面选y - x个放进来，然后里面的全排一下，外面的全排一下就好了喵

这道题的难点全在求逆元和组合数上面了()

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
#define int ll

ll fact[N];    // 阶乘
ll infact[N];  // 阶乘的逆元

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

// 初始化函数：O(N) 时间复杂度
void init() {
    fact[0] = infact[0] = 1;
    
    // 1. 预处理阶乘
    for (int i = 1; i < N; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    // 2. 算出最大阶乘的逆元 (费马小定理)
    infact[N - 1] = qpow(fact[N - 1], MOD - 2);

    // 3. 线性倒推所有逆元 (核心技巧: 1/i! = 1/(i+1)! * (i+1))
    for (int i = N - 2; i >= 1; i--) {
        infact[i] = infact[i + 1] * (i + 1) % MOD;
    }
}

// 计算组合数 C(n, m)
ll C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * infact[m] % MOD * infact[n - m] % MOD;
}

// 计算排列数 A(n, m)
ll A(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * infact[n - m] % MOD;
}

void solve()
{	
    int n;
    cin>>n;
    int x = n / 3;
    if (x == 0) 
    {
        cout<<0<<'\n';
        return;
    }
    int need = n / 2;
    int y = n - x;
    int ans = ((C(y,need - x) * C(x,need - x) % MOD) * fact[x] % MOD) * fact[y] % MOD;
    cout<<ans<<'\n';

    return;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    init();
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}
/*
    ∧＿∧
   (｡•́︿•̀｡)
   /づ正数与负数
 都要开心计算哦
*/