AT_abc405_e 题解

· · 题解

问题描述

给定四种水果的数量：

要求将这 A+B+C+D 个水果排成一排（从左到右），排列必须满足以下条件：

  1. 每个苹果必须排在每个香蕉之前；
  2. 每个苹果必须排在每个葡萄之前；
  3. 每个橙子必须排在每个葡萄之前。

果物之间同种不可区分，所有排列结果取模 998244353 。

核心思想与公式推导

由于题目条件：

我们可以将整个排列分为两部分：

  1. 左侧部分：包含所有苹果、所有橙子以及部分香蕉。
  2. 右侧部分：包含所有葡萄以及剩余的香蕉。

设左侧放香蕉数为 x（其中 x 可以取 0 \le x \le C），则右侧放香蕉数为 C - x。

左侧部分的排列

左侧部分包含：

由于苹果必须全部在香蕉之前，所以苹果和香蕉的相对顺序固定（先 A 个苹果，再 x 个香蕉）。橙子可以插入到这 A+x 个确定位置的任意位置，总数即为 A+B+x 个位置中任选 B 个位置放橙子，因此有：

\text{ways}_{\text{left}}(x) = \binom{A+B+x}{B}.

右侧部分的排列

右侧部分包含：

为满足条件“所有橙子（及苹果）必须在葡萄之前”，右侧部分的第一个位置必须是葡萄。固定后，剩余的葡萄数为 D-1 个，和 C-x 个香蕉共计 (D-1)+(C-x) 个位置，任选 D-1 个位置放葡萄，即：

\text{ways}_{\text{right}}(x) = \binom{(C-x) + D - 1}{D-1}.

总排列数

把左侧和右侧部分的方法数相乘后，对 x 从 0 到 C 求和，即当 D \ge 1 时，总方案数为：

\text{ans} = \sum_{x=0}^{C} \binom{A+B+x}{B} \cdot \binom{(C-x)+(D-1)}{D-1} \pmod{998244353}.

当 D=0（没有葡萄）时，只需满足苹果在香蕉之前：

\text{ans} = \binom{A+B+C}{B} \pmod{998244353}.

详细代码（带注释）

下面是完整的 C++ 代码，代码中利用预处理阶乘和逆阶乘（使用快速幂法计算模逆元），从而快速求组合数。注释部分详细说明了每一步的含义。

#include <iostream>
using namespace std;

typedef long long ll;

const int MOD = 998244353;
// 预处理数组大小，取值足够覆盖题目最大规模，这里取 MAXN = 3000000 + 10
const int MAXN = 3000000 + 10;

int a, b, c, d; // 分别代表苹果、橙子、香蕉、葡萄的数量
ll fact[MAXN], invfact[MAXN];

// 快速幂函数，计算 base^exp mod MOD
inline ll quickPow(ll base, ll exp)
{
    ll cnt = 1;
    while (exp)
    {
        if (exp & 1)
        {
            cnt = cnt * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return cnt;
}

// 预处理 0 到 n 的阶乘和逆阶乘数组
inline void precompute(int n)
{
    fact[0] = 1;
    for (int i = 1; i <= n; ++ i)
    {
        fact[i] = fact[i - 1] * i % MOD;
    }
    // 利用费马小定理计算 fact[n] 的逆元
    invfact[n] = quickPow(fact[n], MOD - 2);
    // 反向递推计算 invfact 数组，从 n 到 0
    for (int i = n; i >= 0; -- i)
    {
        if (i)
        {
            invfact[i - 1] = invfact[i] * i % MOD;
        }
    }
}

// 计算组合数 C(n, k) mod MOD（n 选 k）
inline ll cnm(int n, int k)
{
    if (k < 0 || k > n)
    {
        return 0;
    }
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}

int main()
{
    // 读入水果数量：a=苹果, b=橙子, c=香蕉, d=葡萄
    scanf("%d%d%d%d", &a, &b, &c, &d);

    // 计算预处理上界：
    // 左侧部分最多需要 a+b+c 项；右侧部分需要的最大项为 c+d-1，
    // 取两者较大值作为预处理范围。
    int n1 = a + b + c, 
        n2 = c + d - 1, 
        nmax = n1 > n2 ? n1 : n2;

    // 预处理阶乘与逆阶乘数组，范围 [0, nmax]
    precompute(nmax);

    ll ans = 0;
    // 当没有葡萄时，仅考虑苹果、橙子、香蕉的排序
    if (d == 0)
    {
        ans = cnm(a + b + c, b);
    }
    else
    {
        // 枚举 x：放在左侧的香蕉数，从 0 到 c
        for (int x = 0; x <= c; x++)
        {
            // 左侧部分：
            // 包含 a 个苹果、b 个橙子和 x 个香蕉
            // 由于苹果必须在香蕉前面，其排列方案数为从 (a+b+x) 个位置中选出 b 个位置放橙子
            ll ways1 = cnm(a + b + x, b);

            // 右侧部分：
            // 包含剩余的香蕉（c - x）个和 d 个葡萄，
            // 且为满足条件，右侧部分的第一个位置必须为葡萄，
            // 剩下的有 (c-x) + (d-1) 个位置，从中选择 (d-1) 个放葡萄
            ll ways2 = cnm((c - x) + d - 1, d - 1);

            // 将左右两部分方案数的乘积累加到答案中
            ans = (ans + ways1 * ways2) % MOD;
        }
    }

    // 输出答案（模 MOD）
    printf("%lld\n", ans);

    // 此处 cin >> a; 可用于调试时暂停，但在提交时可以删除
    cin >> a;
    return 0;
}