题解(组合数推导) | #小红的好排列#

分析

定义, 的倍数的位置个数

假设分配给的倍数位置是, 那么分配给非的倍数的位置就是

那么得到等式

得到

那么答案等于

• 个位置里面选择个位置是的倍数的位置
• 里面还剩下个的倍数, 因为位置不是的倍数, 但是是的倍数, 因此整体也是的倍数
• 个位置任意排列
• 个位置任意排列

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, MOD = 1e9 + 7;
const LL INF = 1e18;

int n;
LL fact[N], infact[N];

LL q_pow(LL a, LL b) {
    a %= MOD;
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void init() {
    infact[0] = fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = q_pow(fact[i], MOD - 2);
    }
}

LL C(LL a, LL b) {
    if (a < b || b < 0) return 0;
    return fact[a] * infact[a - b] % MOD * infact[b] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    cin >> n;
    int m = n / 3;
    int k = 2 * m - n / 2;

    if (k < 0 || k > m) {
        cout << 0 << '\n';
        return 0;
    }

    LL ans = C(m, k) * C(n - m, m - k) % MOD * fact[m] % MOD * fact[n - m] % MOD;
    cout << ans << '\n';

    return 0;
}