CF2199H Sum of MEX

一个非负整数序列 $[s_1, s_2, \dots, s_n]$ 的 MEX（Minimum EXcluded number）定义为这个序列中没有出现的最小非负整数。 给定一个数组 $[a_1, a_2, \dots, a_n]$，其中每个元素都是从 $-1$ 到 $n$ 的整数。对于每个 $i$ 从 $1$ 到 $n$，需要计算 $f([a_1, a_2, \dots, a_i])$，其中 $f(s)$ 对于数组 $s$ 定义如下： - 考虑所有可以通过将 $s$ 中等于 $-1$ 的元素替换为 $0$ 到 $n$ 之间的整数得到的不同数组 $s'$； - $f(s)$ 为所有这些数组 $s'$ 的 MEX 值之和。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i \le n$）。 额外输入约束：数组 $a$ 中等于 $-1$ 的元素个数不超过 $300$。

对于每个 $i$ 从 $1$ 到 $n$，输出一个整数——$f([a_1, a_2, \dots, a_i])$，结果需对 $998244353$ 取模。

以第一个示例中的 $i=3$ 为例。我们需要计算 $f([-1, 1, -1])$。可以通过将每个 $-1$ 替换为 $0$ 到 $5$ 的整数，共得到 $36$ 个不同的数组。其中 $25$ 个数组（不包含 $0$ 的）MEX 都为 $0$。来看剩下的 $11$ 个数组： - 数组 $[0, 1, 0]$ 的 MEX 为 $2$； - 数组 $[0, 1, 1]$ 的 MEX 为 $2$； - 数组 $[0, 1, 2]$ 的 MEX 为 $3$； - 数组 $[0, 1, 3]$ 的 MEX 为 $2$； - 数组 $[0, 1, 4]$ 的 MEX 为 $2$； - 数组 $[0, 1, 5]$ 的 MEX 为 $2$； - 数组 $[1, 1, 0]$ 的 MEX 为 $2$； - 数组 $[2, 1, 0]$ 的 MEX 为 $3$； - 数组 $[3, 1, 0]$ 的 MEX 为 $2$； - 数组 $[4, 1, 0]$ 的 MEX 为 $2$； - 数组 $[5, 1, 0]$ 的 MEX 为 $2$。 这些值的和为 $24$。 如果我们考虑 $i=4$，则需要在上述每个数组末尾添加一个 $3$。这样会使其中两个数组的 MEX 增加 $2$，因此 $i=4$ 时的答案为 $26$。 由 ChatGPT 5 翻译