Overview

This is a problem where, in the procedure of converting a box number sequence into a “compressed number sequence,” we count the number of original box number sequences that satisfy the conditions of a partially missing compressed number sequence. We solve this using DP, managing the number of distinct box numbers that have appeared so far as the state.

Analysis

Properties of the Compressed Number Sequence

The compressed number sequence \(C_1, C_2, \dots, C_N\) has important properties. Since compressed numbers are assigned as \(1, 2, 3, \dots\) in order to each “first-appearing box number”:

• When \(C_i\) is a new value (a compressed number appearing for the first time), \(C_i\) must be exactly “the number of distinct box numbers that have appeared so far \(+1\).”
• When \(C_i\) is an existing value, \(C_i\) must be one of the “compressed numbers that have already appeared.”

For example, at \(i=1\), \(C_1\) is always \(1\) (a new value). At \(i=2\), either \(C_2 = 1\) (existing) or \(C_2 = 2\) (new).

Correspondence with Box Number Sequences

Since compressed numbers are a “rename by order of appearance” of box numbers, the degrees of freedom when reconstructing the original box number sequence are as follows:

• When a new compressed number \(k+1\) appears: Choose 1 box from the \(M - k\) unused boxes out of \(M\) total boxes (\(k\) is the current number of distinct types).
• When an existing compressed number \(d \leq k\) is used: The corresponding box is already determined, so there is \(1\) way to choose the box. However, when \(D_i = 0\) (unknown), any of the \(k\) types is acceptable, so there are \(k\) ways.

DP State Design

From the above observations, when processing balls from left to right, the only information needed is “the number of distinct box numbers that have appeared so far, \(k\).”

\(dp[k]\) = the number of ways such that after processing up to ball \(i\), exactly \(k\) distinct box numbers have appeared

Algorithm

The initial state is \(dp[0] = 1\) (at the stage where no balls have been processed, the number of distinct types is 0).

For each ball \(i\), we transition based on the value of \(D_i\):

When \(D_i = 0\) (unknown): There are 2 types of transitions from state \(k\): 1. Use an existing value: Choose one of the \(k\) types → \(dp'[k] \mathrel{+}= dp[k] \times k\) 2. Use a new value: Assign compressed number \(k+1\), choose from \(M-k\) unused boxes → \(dp'[k+1] \mathrel{+}= dp[k] \times (M - k)\)

When \(D_i \neq 0\) (fixed value \(d\)): Transitions from state \(k\): 1. When \(d = k + 1\) (new value): \(dp'[k+1] \mathrel{+}= dp[k] \times (M - k)\) 2. When \(d \leq k\) (existing value): \(dp'[k] \mathrel{+}= dp[k] \times 1\) 3. Otherwise, it is invalid, so no transition occurs.

The final answer is \(\sum_k dp[k]\).

Complexity

• Time complexity: \(O(N \times \min(N, M))\)
  For each ball, the state \(k\) ranges from \(0\) to \(\min(N, M)\). The constraints guarantee that \(N \times \min(N, M) \leq 2.5 \times 10^7\).
• Space complexity: \(O(\min(N, M))\)

Implementation Notes

• The upper bound of \(k\) is \(\min(N, M)\). This is because with \(N\) balls, at most \(N\) distinct types can appear, and there are only \(M\) boxes.

• When \(D_i = d\) is fixed, invalid cases such as \(d > k+1\) or \(d = k+1\) but \(k+1 > K\) naturally result in no transitions, yielding \(0\).

• In Python, speed may be a concern, but skipping when dp[k] == 0 can eliminate unnecessary computations.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    D = [int(input_data[i + 2]) for i in range(N)]
    
    MOD = 998244353
    K = min(N, M)
    
    # dp[k] = number of ways, where k = number of distinct compressed values seen so far
    dp = [0] * (K + 2)
    dp[0] = 1
    
    for i in range(N):
        d = D[i]
        new_dp = [0] * (K + 2)
        
        if d == 0:
            # From state k: stay at k with factor k, or go to k+1 with factor (M-k)
            for k in range(K + 1):
                if dp[k] == 0:
                    continue
                val = dp[k]
                # existing value: k choices
                if k > 0:
                    new_dp[k] = (new_dp[k] + val * k) % MOD
                # new value: (M - k) choices, go to k+1
                if k < K and (M - k) > 0:
                    new_dp[k + 1] = (new_dp[k + 1] + val * (M - k)) % MOD
        else:
            # d is fixed
            for k in range(K + 1):
                if dp[k] == 0:
                    continue
                val = dp[k]
                # Case 1: d = k+1, new value
                if d == k + 1 and k + 1 <= K:
                    new_dp[k + 1] = (new_dp[k + 1] + val * (M - k)) % MOD
                # Case 2: d <= k, existing value
                if d <= k:
                    new_dp[k] = (new_dp[k] + val) % MOD
        
        dp = new_dp
    
    ans = 0
    for k in range(K + 2):
        ans = (ans + dp[k]) % MOD
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.