AtCoder ABC458-E 复盘：隔板建模、非空分组与范德蒙德卷积

发表于 2026-05-18 分类于算法题解/复盘

一道组合计数题的复盘：从相邻限制出发，将原本不易直接处理的排列条件转化为可枚举的结构，并通过组合恒等式化简求和，最终得到可以高效计算的公式。

前言

AtCoder Beginner Contest 458 E 题，周赛中遇到的一道很典型的组合计数题。

刚看到题面时，很容易先产生一个朴素判断：它大概和排列组合有关。但真正开始推导时会发现，如果直接从“所有排列”入手，限制条件并不好处理，公式也不太容易自然写出来。

复盘之后，我觉得这题最值得记录的地方，并不是后续如何用代码计算组合数，而是如何从题目给出的限制中提炼出一个更清晰的计数模型。

这篇文章主要记录从题意理解、结构建模，到最终组合数学公式推出的过程。至于后续如何高效计算组合数，虽然会用到逆元、费马小定理和阶乘逆元预处理，但这些不是本文重点，只在实现部分简单带过。

题意抽象

题目给定三个正整数：

X_1,X_2,X_3

需要统计长度为：

X_1+X_2+X_3

的序列 $A$ 的数量，使得：

序列中恰好有 $X_1$ 个 1；
恰好有 $X_2$ 个 2；
恰好有 $X_3$ 个 3；
任意相邻两个元素的差值绝对值不超过 $1$ 。

也就是说，对于所有满足：

1\le i<X_1+X_2+X_3

的位置，都需要满足：

|a_{i+1}-a_i|\le 1

最后答案需要对 $998244353$ 取模。

由于序列中的元素只有 1、2、3，所以这个相邻限制可以进一步具体化。合法的相邻关系包括：

1	1-1, 1-2, 2-1, 2-2, 2-3, 3-2, 3-3

唯一不合法的是：

1-3, 3-1

因此，题目可以等价转化为：

有 $X_1$ 个 1， $X_2$ 个 2， $X_3$ 个 3，求有多少种排列方式，使得 1 和 3 不直接相邻。

这个转化之后，题目的核心限制就非常清楚了：

2 是可以同时连接 1 和 3 的，而 1 与 3 之间必须被 2 隔开。

用 2 作为隔板

既然 1 和 3 不能相邻，而 2 可以和二者相邻，那么很自然地考虑先把所有 2 放好。

如果有 $X_2$ 个 2，它们会形成：

X_2+1

个空隙。

例如：

1	_ 2 _ 2 _ 2 _ ... 2 _

接下来只需要考虑如何把所有 1 和 3 放进这些空隙中。

这里有一个非常关键的限制：

同一个空隙里不能同时放 1 和 3。

如果某个空隙里既放了 1 又放了 3，无论这个空隙内部怎样排列，都必然会出现 1 和 3 相邻。

比如：

中间会出现 13。

如果写成：

中间会出现 31。

因此，每个空隙只能有三种状态：

1
2
3

只放若干个 1
只放若干个 3
什么都不放

这样，原本的排列问题就被转化成了一个空隙选择问题：

从 $X_2+1$ 个空隙中，选择一部分放 1，选择另一部分放 3，并且两部分不能重合。

固定空隙数量后的计数

设：

a=\text{放 }1\text{ 的空隙数量}

b=\text{放 }3\text{ 的空隙数量}

固定 $a$ 和 $b$ 后，可以分四步计数。

选择放 1 的空隙

总共有 $X_2+1$ 个空隙，需要从中选择 $a$ 个空隙用来放 1。

方案数为：

C(X_2+1,a)

这里的 $C(n,k)$ 表示从 $n$ 个对象中选择 $k$ 个的方案数。

选择放 3 的空隙

放 1 的空隙已经占用了 $a$ 个，剩下还有：

X_2+1-a

个空隙。

由于同一个空隙里不能同时放 1 和 3，所以放 3 的空隙只能从这些剩余空隙中选择。

方案数为：

C(X_2+1-a,b)

把 1 分到选中的空隙中

接下来要把 $X_1$ 个相同的 1 分到 $a$ 个已经选中的空隙里。

注意，这 $a$ 个空隙已经被定义为“用来放 1 的空隙”，所以每个空隙都必须至少放一个 1。如果某个空隙为空，那么它就不应该被计入 $a$ 。

因此，这一步等价于：

把 $X_1$ 个相同元素分成 $a$ 个非空组。

根据插板法，方案数为：

C(X_1-1,a-1)

简单来说，可以把 $X_1$ 个 1 排成一排：

1	1 1 1 ... 1

中间有 $X_1-1$ 个缝。要分成 $a$ 个非空组，就需要从这些缝中选择 $a-1$ 个位置切开，所以方案数为 $C(X_1-1,a-1)$ 。

把 3 分到选中的空隙中

同理，把 $X_3$ 个相同的 3 分到 $b$ 个非空组中，方案数为：

C(X_3-1,b-1)

因此，当 $a,b$ 固定时，对应的方案数为：

C(X_2+1,a) \cdot C(X_2+1-a,b) \cdot C(X_1-1,a-1) \cdot C(X_3-1,b-1)

双重求和公式

接下来考虑 $a,b$ 的枚举范围。

由于一共有 $X_1$ 个 1，而每个被选中的空隙至少需要放一个 1，所以：

1\le a\le X_1

同时，总空隙数只有 $X_2+1$ ，所以：

a\le X_2+1

因此：

1\le a\le \min(X_1,X_2+1)

对于固定的 $a$ ，剩余空隙数为：

X_2+1-a

而放 3 的空隙数量 $b$ 也受到两个限制：

b\le X_3

以及：

b\le X_2+1-a

所以：

1\le b\le \min(X_3,X_2+1-a)

于是可以得到最直接的双重求和公式：

Ans= \sum_{a=1}^{\min(X_1,X_2+1)} \sum_{b=1}^{\min(X_3,X_2+1-a)} C(X_2+1,a) \cdot C(X_2+1-a,b) \cdot C(X_1-1,a-1) \cdot C(X_3-1,b-1)

到这里，计数模型已经完整了。

不过如果按照这个式子直接双重枚举，最坏情况下复杂度会接近：

O(X_1X_3)

而本题中：

X_1,X_2,X_3\le 10^6

因此不能直接使用双重循环。接下来需要把内层关于 $b$ 的求和化简掉。

用范德蒙德卷积化简

固定 $a$ 后，双重求和中与 $b$ 无关的部分是：

C(X_2+1,a)\cdot C(X_1-1,a-1)

与 $b$ 有关的部分是：

\sum_b C(X_2+1-a,b)\cdot C(X_3-1,b-1)

因此，化简的关键就是处理下面这个式子：

\sum_b C(X_2+1-a,b)\cdot C(X_3-1,b-1)

先利用组合数的对称性：

C(n,k)=C(n,n-k)

于是：

C(X_3-1,b-1) = C(X_3-1,(X_3-1)-(b-1))

也就是：

C(X_3-1,b-1)=C(X_3-1,X_3-b)

所以内层求和可以改写为：

\sum_b C(X_2+1-a,b)\cdot C(X_3-1,X_3-b)

这就可以套用范德蒙德卷积：

\sum_i C(A,i)\cdot C(B,K-i)=C(A+B,K)

它的含义是：

从两堆元素中一共选择 $K$ 个。可以枚举从第一堆中选择 $i$ 个，那么就需要从第二堆中选择 $K-i$ 个。把所有 $i$ 的情况加起来，就等价于直接从两堆合并后的元素中选择 $K$ 个。

在这里对应为：

A=X_2+1-a

B=X_3-1

K=X_3

因此：

\sum_b C(X_2+1-a,b)\cdot C(X_3-1,X_3-b) = C((X_2+1-a)+(X_3-1),X_3)

化简括号中的部分：

(X_2+1-a)+(X_3-1)=X_2+X_3-a

所以：

\sum_b C(X_2+1-a,b)\cdot C(X_3-1,b-1) = C(X_2+X_3-a,X_3)

将它代回原来的双重求和，就得到最终公式：

Ans= \sum_{a=1}^{\min(X_1,X_2+1)} C(X_2+1,a) \cdot C(X_1-1,a-1) \cdot C(X_2+X_3-a,X_3)

这样，原本需要枚举 $a,b$ 的双重求和，就被化简成了只需要枚举 $a$ 的单重求和。

手写版推导过程：

公式计算与实现

推出公式之后，剩下的就是大量计算组合数 $C(n,k)$ 。

由于答案需要对 $998244353$ 取模，而 $998244353$ 是质数，所以可以使用费马小定理求逆元，并预处理阶乘与阶乘逆元，使每一次组合数查询为 $O(1)$ 。

整体实现流程为：

1. 预处理 fac[i] = i!
2. 预处理 ifac[i] = (i!)^{-1}
3. 用 C(n,k) = fac[n] * ifac[k] * ifac[n-k] 计算组合数
4. 枚举 a，并按照最终公式累加贡献

这里涉及到的逆元、费马小定理和组合数求值模板不在本文展开，后续会单独整理成组合数学专题。

核心枚举部分对应为：

ll Ans() {
    ll res = 0;
    ll limit = min(x1, x2 + 1);
    for (int i = 1; i <= limit; i++) {
        ll mul = 1;
        mul = mul * C(x2 + 1, i) % MOD;
        mul = mul * C(x1 - 1, i - 1) % MOD;
        mul = mul * C(x2 + x3 - i, x3) % MOD;
        res = (res + mul) % MOD;
    }
    return res;
}

复杂度分析

预处理阶乘和阶乘逆元时，最大只需要处理到：

X_1+X_2+X_3

因此预处理复杂度为：

O(X_1+X_2+X_3)

最终枚举 $a$ 的范围为：

1\le a\le \min(X_1,X_2+1)

所以枚举复杂度为：

O(\min(X_1,X_2+1))

综合来看，总时间复杂度为：

O(X_1+X_2+X_3)

空间复杂度主要来自阶乘数组和阶乘逆元数组，为：

O(X_1+X_2+X_3)

本题数据范围为：

X_1,X_2,X_3\le 10^6

可以通过。

提交记录及 AC 代码

提交记录如下。

点击展开/折叠最终 AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll maxx = 3e6 + 15, MOD = 998244353;

ll x1, x2, x3;
ll fac[maxx], ifac[maxx];

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

ll C(ll n, ll k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

void Init() {
    fac[0] = 1;
    for (int i = 1; i < maxx; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifac[maxx - 1] = qpow(fac[maxx - 1], MOD - 2);
    for (int i = maxx - 1; i >= 1; i--) {
        ifac[i - 1] = ifac[i] * i % MOD;
    }
}

ll Ans() {
    ll res = 0;
    ll limit = min(x1, x2 + 1);
    for (int i = 1; i <= limit; i++) {
        ll mul = 1;
        mul = mul * C(x2 + 1, i) % MOD;
        mul = mul * C(x1 - 1, i - 1) % MOD;
        mul = mul * C(x2 + x3 - i, x3) % MOD;
        res = (res + mul) % MOD;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> x1 >> x2 >> x3;
    Init();
    cout << Ans();
    return 0;
}

结语

这题真正值得复盘的地方，不是组合数如何取模计算，而是如何把原本看起来不太好处理的排列限制转化成一个清晰的计数模型。

整个推导过程可以概括为三步：

先发现唯一非法的相邻关系是 1 和 3；
再用 2 作为隔板，将问题转化为空隙选择与非空分组；
最后用范德蒙德卷积消去一层枚举，得到可以直接实现的单重求和公式。

这题最终用到的代码模板并不复杂，难点在于前面的建模和推导过程：先找出唯一非法的相邻关系，再用隔板把冲突关系转成空隙分配，最后用组合恒等式消掉一层枚举。