题解 | #小红的好排列#

1. 问题分析

1.1 问题抽象

题目要求统计满足特定条件的排列数量：长度为 $n$ 的排列 $a$ 中，恰好有 $n/2$ 个下标 $i$ 满足 $a_i \times i$ 是 3 的倍数。

因为 3 是一个质数，乘积 $a_i \times i$ 被 3 整除的充要条件是： $a_i$ 是 3 的倍数或者 $i$ 是 3 的倍数。

我们可以根据“是否为 3 的倍数”这一属性，将数字 $1 \sim n$ 分为两类集合：

倍数集 (Div3)：包含所有能被 3 整除的数。
- 集合大小设为 $k = \lfloor \frac{n}{3} \rfloor$ 。
非倍数集 (NonDiv3)：包含所有不能被 3 整除的数。
- 集合大小设为 $m = n - k$ 。

1.2 排列位置与值的匹配逻辑

在排列构建过程中，我们需要考虑“下标 $i$ 的属性”和“填入值 $a_i$ 的属性”之间的匹配关系：

如果下标 $i \in \text{Div3}$ （共有 $k$ 个这样的位置）：无论填入什么值 $a_i$ ，乘积 $a_i \times i$ 必然包含因子 3。因此，这 $k$ 个位置必然贡献 $k$ 个满足条件的计数。
如果下标 $i \in \text{NonDiv3}$ （共有 $m$ 个这样的位置）：由于下标本身不含因子 3，为了使乘积成为 3 的倍数，填入的值 $a_i$ 必须属于 $\text{Div3}$ 集合。

1.3 目标确定

题目要求总共有 $T = \frac{n}{2}$ 个满足条件的位置。已知来自 $\text{Div3}$ 下标的贡献是固定的 $k$ 个。因此，我们需要从 $\text{NonDiv3}$ 下标的位置中，额外凑出 $x$ 个满足条件的位置，其中： $x = T - k = \frac{n}{2} - \lfloor \frac{n}{3} \rfloor$

如果计算出的 $x < 0$ ，说明即使没有任何 $\text{NonDiv3}$ 下标贡献，总数也超过了 $n/2$ ，此时无解（但根据 $n \ge 2$ ，这种情况不会发生，因为 $k \le n/2$ ）。

2. 算法：组合计数

我们需要计算满足上述结构的排列总数。问题转化为两部分的填充任务。

在 NonDiv3 下标中构造 $x$ 个“好”位置：
- 选位置：从 $m$ 个 $\text{NonDiv3}$ 下标中选出 $x$ 个位置。
  - 方案数： $C(m, x)$ 。
- 选值并排列：这 $x$ 个位置必须填入 $\text{Div3}$ 的值。我们从 $k$ 个可用的 $\text{Div3}$ 值中选出 $x$ 个，并排列放入这 $x$ 个位置。
  - 方案数： $P(k, x) = \frac{k!}{(k-x)!}$ 。
填充剩余的 NonDiv3 下标：
- 剩余的 $\text{NonDiv3}$ 下标数量为 $m - x$ 。
- 为了不增加满足条件的计数，这些位置严禁填入剩余的 $\text{Div3}$ 值，必须填入 $\text{NonDiv3}$ 值。
- 我们有 $m$ 个 $\text{NonDiv3}$ 值可用，从中选出 $m-x$ 个并在这些位置排列。
- 方案数： $P(m, m-x) = \frac{m!}{x!}$ 。
填充 Div3 下标：
- 此时，剩余的空位是 $k$ 个 $\text{Div3}$ 下标位置。
- 剩余的待填数字总数也是 $k$ 个（包括剩余的 $\text{Div3}$ 值和剩余的 $\text{NonDiv3}$ 值）。
- 由于这些位置的下标已经是 3 的倍数，无论填什么都满足条件（已经被计入基础贡献 $k$ 中），因此只需将剩余数字任意全排列。
- 方案数： $k!$ 。

最终公式

根据乘法原理，总方案数为各步骤方案数的乘积： $\text{Ans} = C(m, x) \times P(k, x) \times P(m, m-x) \times k!$

展开组合数和排列数公式： $\text{Ans} = \frac{m!}{x!(m-x)!} \times \frac{k!}{(k-x)!} \times \frac{m!}{x!} \times k!$

注意：如果 $x > k$ （需要的 $\text{Div3}$ 值比拥有的多）或者 $x < 0$ ，答案为 0。

3. 复杂度分析

3.1 时间复杂度

预处理：我们需要计算阶乘及其模逆元（用于组合数计算）。范围是 $N=10^6$ 。
- 计算阶乘数组 frac[]： $O(N)$ 。
- 计算逆元数组 inv[]：利用费马小定理 + 线性递推或快速幂，整体预处理可以是 $O(N)$ 。
单次查询：公式计算仅涉及常数次乘法和取模操作。
- 计算耗时： $O(1)$ 。
总时间复杂度： $O(N)$ 。

3.2 空间复杂度

如果不使用线性求逆元，仅存储阶乘表，需要 $O(N)$ 空间。
如果存储阶乘和逆元表，需要 $O(N)$ 空间。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

struct Combinatorics {
    std::vector<ll> fact;
    std::vector<ll> invFact;

    Combinatorics(int n) {
        fact.resize(n + 1);
        invFact.resize(n + 1);

        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        // 使用费马小定理计算 n! 的逆元
        invFact[n] = power(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; --i) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    // 快速幂
    ll power(ll base, ll exp) const {
        ll res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    // 查询组合数 C(n, k)
    ll nCr(int n, int k) const {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    Combinatorics comb(n);
    ll k = n / 3;
    ll m = n - k;
    ll x = n / 2 - k;
    if (x < 0 || x > k || x > m) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1LL;
    // 在 NonDiv3 下标中构造 x 个“好”位置
    ans = ans * comb.nCr(m, x) % MOD;
    ans = (ans * comb.fact[k] % MOD) * comb.invFact[k - x] % MOD;
    // 填充剩余的 NonDiv3 下标
    ans = (ans * comb.fact[m] % MOD) * comb.invFact[x] % MOD;
    // 填充 Div3 下标
    ans = ans * comb.fact[k] % MOD;

    cout << ans << endl;
}