← 返回题目列表

Codeforces · 2199/H

H. MEX 总和

中文机器翻译题面 查看原题

非负整数序列 $$$[s_1, s_2, \dots, s_n]$$$ 的 MEX 是未出现在该序列中的最小非负整数。

给定一个数组 $$$[a_1, a_2, \dots, a_n]$$$,其中每个元素都是从 $$$-1$$$ 到 $$$n$$$ 的整数。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,计算 $$$f([a_1, a_2, \dots, a_i])$$$,其中数组 $$$s$$$ 的 $$$f(s)$$$ 定义如下:

  • 考虑通过用从 $$$0$$$ 到 $$$n$$$ 的整数替换所有等于 $$$-1$$$ 的元素,可以从数组 $$$s$$$ 获得所有不同的数组 $$$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$$$ 包含不超过 $$$300$$$ 等于 $$$-1$$$ 的元素。

输出

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,输出一个整数 — $$$f([a_1, a_2, \dots, a_i])$$$,以 $$$998244353$$$ 为模。

示例

输入
复制

5
-1 1 -1 3 -1

输出
复制

1 2 24 26 248 

输入
复制

7
3 5 -1 -1 -1 -1 1

输出
复制

0 0 1 17 223 2645 4906 

输入
复制

10
3 8 5 1 0 0 7 2 2 8

输出
复制

0 0 0 0 2 2 2 4 4 4 

注意

考虑第一个示例中的 $$$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$$$。