Overview

We count using a DP whose state only tracks “how many distinct boxes have been used so far.” Due to the properties of compressed numbering, whether the next ball “goes into an already-seen box” or “goes into a new box” can be determined and computed solely from the number of distinct boxes used \(k\).

Analysis

The essence of this problem is that trying to directly reconstruct the actual box number sequence \(B\) leads to too many cases. Since each \(B_i\) can range from \(1\) to \(M\), naively trying all possibilities gives \(M^N\) combinations, which is far too many.

Key Observation 1: Compressed numbers follow “order of first appearance”

In the compressed number sequence, if exactly \(k\) distinct boxes have appeared up to a certain point, then the assigned compressed numbers are necessarily \(1, 2, \dots, k\).

For example, if 3 distinct boxes have appeared so far, then there exists exactly one box each for:

• Compressed number 1
• Compressed number 2
• Compressed number 3

In other words, as long as we know “how many distinct boxes have appeared so far”:

• When using an existing compressed number \(x\), the box is uniquely determined
• When creating a new compressed number, we choose from actual box numbers not yet used

Key Observation 2: The state “number of distinct boxes used” is sufficient

Define \(f_i[k]\) as:

• After examining the first \(i\) items
• The conditions are satisfied
• The number of distinct actual box numbers used is exactly \(k\)

the number of such box number sequences.

This state is sufficient because the choices for the next step are determined solely by \(k\).

When \(D_i = 0\) (compressed number is unknown)

The next ball can be:

• Placed in one of the \(k\) boxes already used \(\Rightarrow\) \(k\) choices
• Placed in a box not yet used \(\Rightarrow\) \(M-k\) choices

Either option is valid.

When \(D_i = x \neq 0\) (compressed number is specified)

The next compressed number must be \(x\).

• If \(k \ge x\) distinct boxes have already been used, the box with compressed number \(x\) is uniquely determined \(\Rightarrow\) 1 choice
• If only \(x-1\) distinct boxes have been used, compressed number \(x\) must appear for the first time now \(\Rightarrow\) A new box must be chosen, giving \(M-(x-1)\) choices
• If \(x > k+1\), it is impossible (At most one new compressed number can be added at a time)

This is the crux of the problem. Without needing to track details like “which actual box number corresponds to compressed number 2,” we can transition based on count alone using just \(k\).

---

Why a naive DP is difficult

For instance, if we include “the set of actual box numbers used so far” or “the mapping between compressed numbers and actual box numbers” in the state, the number of states explodes. However, from the observations above, all we need is “how many distinct types have been used.” This reduces the number of states to \(O(\min(N, M))\).

Algorithm

DP Definition

Define \(f_i[k]\) as the number of sequences where “after examining the first \(i\) items, the conditions are satisfied, and the number of distinct box types used is exactly \(k\).”

Initial values:

• \(f_0[0] = 1\)
• All others are \(0\)

---

Transition 1: When \(D_i = 0\)

The compressed number is unknown, so we may use either an existing box or a new box.

There are 2 ways to end up with exactly \(k\) distinct types:

1. We already had \(k\) types and use one of them this time → \(k\) choices
2. We had \(k-1\) types and use a new box this time → There are \(M-(k-1) = M-k+1\) unused boxes

Therefore:

\[ f_i[k] = k \cdot f_{i-1}[k] + (M-k+1)\cdot f_{i-1}[k-1] \]

---

Transition 2: When \(D_i = x \neq 0\)

The compressed number this time must be \(x\).

\(k < x\)

To produce compressed number \(x\), at least \(x\) distinct boxes are needed, so this is impossible.

\(k = x\)

There are 2 cases:

1. We already had \(x\) types, and we use the box with compressed number \(x\) → 1 choice
2. We had \(x-1\) types, and we introduce a new box which becomes compressed number \(x\) → \(M-x+1\) choices

Therefore:

\[ f_i[x] = f_{i-1}[x] + (M-x+1)\cdot f_{i-1}[x-1] \]

\(k > x\)

The box with compressed number \(x\) already exists, so we must use it. Therefore:

\[ f_i[k] = f_{i-1}[k] \quad (k > x) \]

---

Impossibility Detection

If the specified value \(x = D_i\) satisfies:

• \(x > M\) (There are only \(M\) types of boxes)
• Letting \(\text{lim}\) be the current maximum reachable number of types, \(x > \text{lim}+1\) (At most one new compressed number can be added at a time)

then the answer is \(0\) at that point.

---

Implementation Details

In the code, instead of maintaining the entire 2D DP, we only keep the current row as a 1D array dp.

• dp[k]: the count for exactly \(k\) distinct types at the current prefix
• lim: the maximum number of distinct types currently reachable

For each \(i\), we create a new array new and perform the update. At the end, taking sum(dp) gives the answer, since the final number of distinct types can be anything.

Complexity

• Time complexity: \(O(N \cdot \min(N, M))\)
• Space complexity: \(O(\min(N, M))\)

Given the constraint \(N \times \min(N, M) \le 2.5 \times 10^7\), this DP is efficient enough.

Implementation Notes

• The initial state is “nothing has been seen yet, so 0 types,” with dp[0] = 1.

• When \(D_i = x\), if \(x > M\) or \(x > \text{lim} + 1\), immediately output 0.

• lim is maintained separately to represent “whether a state is reachable.” Since the DP values are stored modulo \(998244353\), a value happening to be 0 does not necessarily mean “impossible.”

• When \(D_i = 0\) and lim = M, note that no more new boxes can be added.

  Source Code

import sys

MOD = 998244353

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    D = data[2:2 + N]

    dp = [1]   # dp[k]: count for current prefix using exactly k distinct boxes
    lim = 0    # maximum reachable k (existence-wise, not modulo)

    mod = MOD
    m = M

    for d in D:
        if d == 0:
            prev = dp
            l = lim
            if l < m:
                new = [0] * (l + 2)
                for k in range(1, l + 1):
                    new[k] = (prev[k] * k + prev[k - 1] * (m - k + 1)) % mod
                new[l + 1] = prev[l] * (m - l) % mod
                dp = new
                lim = l + 1
            else:
                new = [0] * (l + 1)
                for k in range(1, l + 1):
                    new[k] = (prev[k] * k + prev[k - 1] * (m - k + 1)) % mod
                dp = new
        else:
            x = d
            if x > m or x > lim + 1:
                print(0)
                return

            prev = dp
            l = lim
            if x <= l:
                new = [0] * (l + 1)
                new[x:l + 1] = prev[x:l + 1]
                new[x] = (new[x] + prev[x - 1] * (m - x + 1)) % mod
                dp = new
            else:
                # x == l + 1
                new = [0] * (x + 1)
                new[x] = prev[l] * (m - l) % mod
                dp = new
                lim = x

    print(sum(dp) % mod)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.