← 返回题目列表

Codeforces · 1158/F

F. 子阵列的密度

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

设 $$$c$$$ 为某个正整数。我们称正整数数组 $$$a_1, a_2, \ldots, a_n$$$ 为 $$$c$$$ 数组,如果对于所有 $$$i$$$ 条件 $$$1 \leq a_i \leq c$$$ 都满足。我们称 $$$c$$$-array $$$b_1, b_2, \ldots, b_k$$$ 为 $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$ 的子数组,如果存在这样一组 $$$k$$$ 索引 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ $$$b_j = a_{i_j}$$$ 对于所有 $$$1 \leq j \leq k$$$。让我们将 $$$c$$$ 数组 $$$a_1, a_2, \ldots, a_n$$$ 的密度定义为最大非负整数 $$$p$$$,这样任何包含 $$$p$$$ 数字的 $$$c$$$ 数组都是 $$$a_1, a_2, \ldots, a_n$$$ 的子数组。

给你一个数字 $$$c$$$ 和一些 $$$c$$$ 数组 $$$a_1, a_2, \ldots, a_n$$$。对于所有 $$$0 \leq p \leq n$$$,找到索引序列的数量 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ 对于所有 $$$1 \leq k \leq n$$$,使得数组 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 的密度等于$$$p$$$。通过模 $$$998\,244\,353$$$ 找到这些数字,因为它们可能太大。

输入

第一行包含两个整数 $$$n$$$ 和 $$$c$$$,用空格分隔 ($$$1 \leq n, c \leq 3\,000$$$)。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,用空格分隔 ($$$1 \leq a_i \leq c$$$)。

输出

打印 $$$n + 1$$$ 数字 $$$s_0, s_1, \ldots, s_n$$$。对于所有 $$$1 \leq k \leq n$$$,$$$s_p$$$ 应等于索引序列 $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ 模 $$$998\,244\,353$$$,这样数组的密度 $$$a_{i_1}, a_{i_2}, \ldots,a_{i_k}$$$ 等于$$$p$$$。

示例

输入 #1

4 1
1 1 1 1

输出 #1

0 4 6 4 1

输入 #2

3 3
1 2 3

输出 #2

6 1 0 0

输入 #3

5 2
1 2 1 2 1

输出 #3

10 17 4 0 0 0

注意

在第一个示例中,很容易看出数组的密度始终等于其长度。存在具有一个索引的 $$$4$$$ 序列,具有两个索引的 $$$6$$$,具有三个索引的 $$$4$$$ 和具有四个索引的 $$$1$$$。

在第二个示例中,使数组具有非零密度的唯一索引序列是所有索引,因为在其他情况下,数组中不会有至少一个从 $$$1$$$ 到 $$$3$$$ 的数字,因此它不会满足 $$$p \geq 1$$$ 的密度条件。