CF1158F Density of subarrays

给定一个正整数 $c$。如果一个正整数数组 $a_1, a_2, \ldots, a_n$ 满足对所有 $i$ 都有 $1 \leq a_i \leq c$，则称其为 $c$-数组。若存在一组 $k$ 个下标 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$，使得 $b_j = a_{i_j}$ 对所有 $1 \leq j \leq k$ 成立，则称 $c$-数组 $b_1, b_2, \ldots, b_k$ 是 $c$-数组 $a_1, a_2, \ldots, a_n$ 的一个子序列。 定义 $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$，求出满足密度为 $p$ 的所有下标序列 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$（$1 \leq k \leq n$）的个数。由于答案可能很大，请对 $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$。其中 $s_p$ 表示所有密度为 $p$ 的下标序列 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$（$1 \leq k \leq n$）的个数，对 $998\,244\,353$ 取模。

在第一个样例中，可以很容易看出数组的密度总是等于其长度。存在 $4$ 个只包含一个下标的序列，$6$ 个包含两个下标的序列，$4$ 个包含三个下标的序列，以及 $1$ 个包含四个下标的序列。 在第二个样例中，唯一密度大于 $0$ 的下标序列是包含所有下标的那个序列，因为其他情况下数组中至少缺少 $1$ 到 $3$ 中的某个数，因此对于 $p \geq 1$ 不满足密度条件。 由 ChatGPT 4.1 翻译