Sum of MEX

Research note: I checked the official Codeforces Kotlin Heroes 14 editorial page at https://codeforces.com/blog/entry/151783. Its written tutorial for 2199H is empty, but it includes the setter solution; the explanation below is derived from that code and the supplied statement, not copied text.

Let a prefix contain $c$ wildcards. Look only at the fixed values already present. Write the missing values in increasing order:

$b_0 < b_1 < b_2 < ...$

The final MEX can only be one of these $b$ values, because fixed present values never disappear.

Suppose the final MEX is $b_j$. Then every smaller missing value $b_0, ..., b_{j-1}$ has to be created by at least one wildcard, and $b_j$ must be avoided by every wildcard. If $j > c$, this is impossible; $c$ positions cannot cover $j$ distinct missing values. So only the first $c+1$ missing values matter. This is the whole trick; tracking actual completed arrays directly is a swamp.

Now count completions. Original wildcard choices are $0..n$, so there are $n+1$ values. For MEX $b_j$, value $b_j$ is forbidden, leaving exactly $n$ allowed choices. Among those allowed choices, exactly $j$ values are special: $b_0, ..., b_{j-1}$, and all must appear at least once. The count depends only on $j$ and $c$, not on the actual numeric value of $b_j$.

For a fixed need = j, define $dp_i[x]$ as the number of ways after filling $i$ wildcard positions such that exactly $x$ of the required values have appeared. Initially $dp_0[0]=1$. From state $x$:

• choose one of the need - x required values not seen yet, moving to $x+1$;
• choose anything else, staying at $x$. There are $n - (need - x)$ such choices.

So the transitions are:

$dp_{i+1}[x+1] += dp_i[x](need-x)$

$dp_{i+1}[x] += dp_i[x](n-(need-x))$

All operations are modulo $998244353$. Let $ways[need][c] = dp_c[need]$.

For a prefix with $c$ wildcards and first missing values $b_0, ..., b_c$, the answer is:

$ans = \sum_{j=0}^{c} ways[j][c] b_j$

These cases are disjoint and exhaustive: every completed array has exactly one first missing fixed-absent value, and that rank determines its MEX.

To maintain the $b_j$ values, use two ordered sets. small stores the first $c+1$ currently missing values, and rest stores the remaining missing values. Initially, rest contains $0..n$. When a fixed value appears, erase it from whichever set contains it. When a wildcard appears, increment $c$. After each update, move smallest values from rest into small until small.size() = c+1. Iterating small gives $b_0, ..., b_c$ in order.

Edge cases behave naturally. With no wildcards, $c=0$, so the formula returns the ordinary MEX. For $j=0$, there are no required smaller missing values; we only avoid $b_0$, giving $n^c$ completions. Duplicates of fixed values do nothing after the first occurrence, as they should.

Let $k$ be the total number of -1 values. The DP costs $O(k^3)$, with $k <= 300$. Maintaining prefixes costs $O(n \log n + nk)$ because each prefix sums over at most $k+1$ missing values. Memory is $O(k^2+n)$.