Introduction

Problem E from AtCoder Beginner Contest 458 is a very typical combinatorial counting problem I encountered in a weekly contest.

On first reading the statement, it is easy to make a rough guess that permutations and combinations must be involved. But once you start deriving a solution, you find that starting directly from “all arrangements” makes the constraints awkward to handle, and a formula does not emerge so naturally.

After reviewing it, I felt that the part most worth recording was how to extract a clearer counting model from the constraints, rather than how to calculate binomial coefficients in code afterward.

This article mainly records the process from understanding the statement and modeling the structure to deriving the final combinatorial formula. Efficiently evaluating binomial coefficients does involve modular inverses, Fermat’s little theorem, and precomputed inverse factorials, but those are not the focus here; I only touch on them in the implementation section.

Modeling the Problem

The problem gives three positive integers:

We need to count sequences $A$ of length:

that satisfy:

• The sequence contains exactly $X_1$ copies of 1;
• Exactly $X_2$ copies of 2;
• Exactly $X_3$ copies of 3;
• The absolute difference between any two adjacent elements is at most $1$.

In other words, every position satisfying:

must satisfy:

The final answer is taken modulo $998244353$.

Since the only elements are 1, 2, and 3, we can state the adjacency constraint more concretely. The allowed adjacent pairs are:

1

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

The only forbidden pairs are:

1

1-3, 3-1

The problem is therefore equivalent to:

Given $X_1$ copies of 1, $X_2$ copies of 2, and $X_3$ copies of 3, how many arrangements have no 1 directly adjacent to a 3?

This makes the central restriction very clear:

A 2 can sit next to either 1 or 3, while 1 and 3 must be separated by 2.

Using 2 as a Separator

Since 1 and 3 cannot be adjacent, whereas 2 can be adjacent to both, it is natural to place all the 2s first.

With $X_2$ copies of 2, the number of gaps they create is:

For example:

1

_ 2 _ 2 _ 2 _ ... 2 _

We then only need to decide how to place all the 1s and 3s into these gaps.

There is one crucial restriction:

A single gap cannot contain both 1 and 3.

If a gap contains both, some 1 and 3 must become adjacent, no matter how we arrange the contents of that gap.

For example:

1

111333

has 13 in the middle.

If we write:

1

333111

there is a 31 in the middle.

Each gap therefore has only three possible states: some 1s only, some 3s only, or nothing:

1
2
3

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

The original arrangement problem has now become a gap-selection problem:

Among the $X_2+1$ gaps, choose some for 1 and some others for 3, with no overlap between the two selections.

Counting with Fixed Numbers of Gaps

Let $a$ be the number of gaps containing 1, and $b$ the number containing 3:

Once $a$ and $b$ are fixed, we can count in four steps.

Choose the Gaps for 1

There are $X_2+1$ gaps in total, and we choose $a$ of them for 1.

The number of choices is:

Here, $C(n,k)$ denotes the number of ways to choose $k$ objects from $n$.

Choose the Gaps for 3

The gaps for 1 have already occupied $a$ places, leaving:

gaps.

Since a gap cannot contain both 1 and 3, we must choose the gaps for 3 from those remaining.

The number of choices is:

Distribute the 1s Among Their Chosen Gaps

Next, distribute $X_1$ identical copies of 1 among the $a$ chosen gaps.

These $a$ gaps have already been designated as gaps containing 1, so each must receive at least one 1. If a gap were empty, it should not have been included in $a$.

This step is therefore equivalent to:

Splitting $X_1$ identical elements into $a$ nonempty groups.

By stars and bars, the number of ways is:

To see this directly, line up the $X_1$ copies of 1:

1

1 1 1 ... 1

There are $X_1-1$ spaces between them. Splitting them into $a$ nonempty groups means choosing $a-1$ of these spaces as cuts, giving $C(X_1-1,a-1)$ ways.

Distribute the 3s Among Their Chosen Gaps

Similarly, splitting $X_3$ identical copies of 3 into $b$ nonempty groups gives:

Thus, for fixed $a,b$, the number of arrangements is:

The Double-Sum Formula

Next, consider the ranges of $a,b$.

There are $X_1$ copies of 1, and each selected gap needs at least one, so:

There are also only $X_2+1$ gaps in total, so:

Hence:

For a fixed $a$, the number of remaining gaps is:

The number $b$ of gaps containing 3 has two bounds as well:

and:

Thus:

This gives the most direct double-sum formula:

At this point, the counting model is complete.

However, directly enumerating both variables in this formula would have a worst-case complexity approaching:

The constraints are:

so a double loop is infeasible. We need to simplify away the inner sum over $b$.

Simplifying with Vandermonde’s Convolution

For a fixed $a$, the part of the double sum independent of $b$ is:

The part involving $b$ is:

The key to the simplification is therefore the following expression:

First, use the symmetry of binomial coefficients:

Then:

That is:

The inner sum can therefore be rewritten as:

Now we can apply Vandermonde’s convolution:

Its meaning is:

Choose a total of $K$ elements from two groups. If we enumerate the number $i$ chosen from the first group, we must choose $K-i$ from the second. Summing over all $i$ is equivalent to choosing $K$ elements directly from the combined groups.

Here, the correspondence is:

Therefore:

Simplify the expression inside the parentheses:

So:

Substituting this into the original double sum gives the final formula:

The double sum over $a,b$ has become a single sum over $a$.

Here is the handwritten derivation:

Image legend: a: 放1 means the number of gaps containing 1, and b: 放3 the number containing 3. 提b isolates the sum over b; 即 means “that is”; 代回 means “substitute back.” The intermediate labels are $Y=X_2+1-a$ and $Z=X_3-1$.

Evaluating the Formula and Implementing It

With the formula derived, the remaining task is to evaluate many binomial coefficients $C(n,k)$.

The answer is taken modulo $998244353$, and $998244353$ is prime. We can therefore use Fermat’s little theorem to find inverses and precompute factorials and inverse factorials, making each binomial-coefficient query $O(1)$.

The implementation proceeds as follows. Precompute fac[i] = i!, then ifac[i] = (i!)^{-1}; evaluate binomial coefficients with C(n,k) = fac[n] * ifac[k] * ifac[n-k]; finally, enumerate a and accumulate contributions using the final formula:

1
2
3
4

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

I will not expand on modular inverses, Fermat’s little theorem, or the binomial-coefficient template here. I plan to collect those separately in a combinatorics topic summary.

The main enumeration is:

1
2
3
4
5
6
7
8
9
10
11
12

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

Complexity Analysis

When precomputing factorials and inverse factorials, the largest index we need is:

The preprocessing complexity is therefore:

The final range for enumerating $a$ is:

so the enumeration takes:

Overall, the total time complexity is:

The main space cost comes from the factorial and inverse-factorial arrays:

The constraints are:

This is sufficient to pass.

Submission Record and Accepted Code

The submission record is shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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

Closing Thoughts

The part of this problem worth reviewing is how to turn an initially awkward restriction on arrangements into a clear counting model, rather than how to evaluate binomial coefficients modulo a prime.

The derivation can be summarized in three steps:

• Recognize that the only forbidden adjacency is between 1 and 3;
• Use 2 as a separator, turning the problem into choosing gaps and forming nonempty groups;
• Apply Vandermonde’s convolution to remove one level of enumeration and obtain a single-sum formula ready to implement.

The final code templates are not complicated. The difficult part comes earlier, in the modeling and derivation: identify the only forbidden adjacency, use separators to turn the conflict into gap allocation, and then use a combinatorial identity to eliminate one level of enumeration.