CF1158F.Density of subarrays

Let $c$ be some positive integer. Let's call an array $a_1, a_2, \ldots, a_n$ of positive integers $c$-array, if for all $i$ condition $1 \leq a_i \leq c$ is satisfied. Let's call $c$-array $b_1, b_2, \ldots, b_k$ a subarray of $c$-array $a_1, a_2, \ldots, a_n$, if there exists such set of $k$ indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$ that $b_j = a_{i_j}$ for all $1 \leq j \leq k$. Let's define density of $c$-array $a_1, a_2, \ldots, a_n$ as maximal non-negative integer $p$, such that any $c$-array, that contains $p$ numbers is a subarray of $a_1, a_2, \ldots, a_n$.

You are given a number $c$ and some $c$-array $a_1, a_2, \ldots, a_n$. For all $0 \leq p \leq n$ find the number of sequences of indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$ for all $1 \leq k \leq n$, such that density of array $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ is equal to $p$. Find these numbers by modulo $998\,244\,353$, because they can be too large.

设 $c$ 为某个正整数。若一个由正整数组成的数组 $a_1, a_2, \ldots, a_n$ 满足对所有 $i$ 均有 $1 \leq a_i \leq c$，则称其为 $c$-数组。
设 $b_1, b_2, \ldots, b_k$ 是一个 $c$-数组，若存在一组下标 $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$，使得对所有 $1 \leq j \leq k$ 都有 $b_j = a_{i_j}$，则称该 $c$-数组为 $c$-数组 $a_1, a_2, \ldots, a_n$ 的一个子序列（subarray）。
定义 $c$-数组 $a_1, a_2, \ldots, a_n$ 的密度为最大的非负整数 $p$，使得任意长度为 $p$ 的 $c$-数组（即含 $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 \lt i_2 \lt \ldots \lt i_k \leq n$（其中 $1 \leq k \leq n$）的个数：子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 的密度恰好等于 $p$。
由于结果可能非常大，请对 $998\,244\,353$ 取模输出这些数值。

The first line contains two integers $n$ and $c$, separated by spaces ($1 \leq n, c \leq 3\,000$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, separated by spaces ($1 \leq a_i \leq c$).

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

Print $n + 1$ numbers $s_0, s_1, \ldots, s_n$. $s_p$ should be equal to the number of sequences of indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$ for all $1 \leq k \leq n$ by modulo $998\,244\,353$, such that the density of array $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ is equal to $p$.

输出 $n + 1$ 个数 $s_0, s_1, \ldots, s_n$。对每个 $p$，$s_p$ 应等于满足如下条件的下标序列 $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$（其中 $1 \leq k \leq n$）的个数，结果对 $998\,244\,353$ 取模：子数组 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 的密度恰好为 $p$。

In the first example, it's easy to see that the density of array will always be equal to its length. There exists $4$ sequences with one index, $6$ with two indices, $4$ with three and $1$ with four.

In the second example, the only sequence of indices, such that the array will have non-zero density is all indices because in other cases there won't be at least one number from $1$ to $3$ in the array, so it won't satisfy the condition of density for $p \geq 1$.

在第一个例子中，很容易看出数组的密度始终等于其长度。长度为 $1$ 的索引序列有 $4$ 个，长度为 $2$ 的有 $6$ 个，长度为 $3$ 的有 $4$ 个，长度为 $4$ 的有 $1$ 个。

在第二个例子中，唯一能使数组具有非零密度的索引序列是包含全部索引的序列，因为其他情况下数组中至少缺少 $1$ 到 $3$ 中的一个数，从而无法满足 $p \geq 1$ 时的密度条件。