Slime and Sequences (Easy Version)
题意翻译
对于正整数序列 $p$,定义 $p$ 是好的,当且仅当如果 $k$ 在 $p$ 中出现过,那么在 $k$ 的最后一次出现之前,有 $k-1$ 出现过。
设所有长度为 $n$ 的好的序列组成的集合为 $S_n$。对于序列 $p$ 和正整数 $i$ 定义 $f_p(i)$ 为 $i$ 在 $p$ 中出现的次数。现在请你对于所有 $i \in [1,n]$,求出
$$\sum_{p \in S_n} f_p(i)$$
对 $998\ 244\ 353$ 取模的结果。
$n\le 5000$
_Translated by Caro23333_
题目描述
Note that the only differences between easy and hard versions are the constraints on $ n $ and the time limit. You can make hacks only if all versions are solved.
Slime is interested in sequences. He defined good positive integer sequences $ p $ of length $ n $ as follows:
- For each $ k>1 $ that presents in $ p $ , there should be at least one pair of indices $ i,j $ , such that $ 1 \leq i < j \leq n $ , $ p_i = k - 1 $ and $ p_j = k $ .
For the given integer $ n $ , the set of all good sequences of length $ n $ is $ s_n $ . For the fixed integer $ k $ and the sequence $ p $ , let $ f_p(k) $ be the number of times that $ k $ appears in $ p $ . For each $ k $ from $ 1 $ to $ n $ , Slime wants to know the following value:
$ $$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353 $ $$$
输入输出格式
输入格式
The first line contains one integer $ n\ (1\le n\le 5000) $ .
输出格式
Print $ n $ integers, the $ i $ -th of them should be equal to $ \left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353 $ .
输入输出样例
输入样例 #1
2
输出样例 #1
3 1
输入样例 #2
3
输出样例 #2
10 7 1
输入样例 #3
1
输出样例 #3
1
说明
In the first example, $ s=\{[1,1],[1,2]\} $ .
In the second example, $ s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\} $ .
In the third example, $ s=\{[1]\} $ .