题解 | #小红的好排列#

1. 问题分析

1.1 问题抽象

题目要求统计满足特定条件的排列数量：长度为 的排列 中，恰好有 个下标 满足 是 3 的倍数。

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

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

1. 倍数集 (Div3)：包含所有能被 3 整除的数。
   • 集合大小设为 。
2. 非倍数集 (NonDiv3)：包含所有不能被 3 整除的数。
   • 集合大小设为 。

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

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

• 如果下标 （共有 个这样的位置）： 无论填入什么值 ，乘积 必然包含因子 3。因此，这 个位置必然贡献 个满足条件的计数。

• 如果下标 （共有 个这样的位置）： 由于下标本身不含因子 3，为了使乘积成为 3 的倍数，填入的值 必须属于 集合。

1.3 目标确定

题目要求总共有 个满足条件的位置。 已知来自 下标的贡献是固定的 个。 因此，我们需要从 下标的位置中，额外凑出 个满足条件的位置，其中：

如果计算出的 ，说明即使没有任何 下标贡献，总数也超过了 ，此时无解（但根据 ，这种情况不会发生，因为 ）。

2. 算法：组合计数

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

1. 在 NonDiv3 下标中构造 个“好”位置：

   • 选位置：从 个 下标中选出 个位置。
     • 方案数：。
   • 选值并排列：这 个位置必须填入 的值。我们从 个可用的 值中选出 个，并排列放入这 个位置。
     • 方案数：。

2. 填充剩余的 NonDiv3 下标：

   • 剩余的 下标数量为 。
   • 为了不增加满足条件的计数，这些位置严禁填入剩余的 值，必须填入 值。
   • 我们有 个 值可用，从中选出 个并在这些位置排列。
   • 方案数：。

3. 填充 Div3 下标：

   • 此时，剩余的空位是 个 下标位置。
   • 剩余的待填数字总数也是 个（包括剩余的 值和剩余的 值）。
   • 由于这些位置的下标已经是 3 的倍数，无论填什么都满足条件（已经被计入基础贡献 中），因此只需将剩余数字任意全排列。
   • 方案数：。

最终公式

根据乘法原理，总方案数为各步骤方案数的乘积：

展开组合数和排列数公式：

注意：如果 （需要的 值比拥有的多）或者 ，答案为 0。

3. 复杂度分析

3.1 时间复杂度

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

3.2 空间复杂度

• 如果不使用线性求逆元，仅存储阶乘表，需要 空间。
• 如果存储阶乘和逆元表，需要 空间。

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;
}