Slime and Sequences (Easy Version)
Contest: Codeforces Round 641 (Div. 1)
Difficulty rating: 3100
Tags: dp, fft, math

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$$$$$$

Input format:
The first line contains one integer $$$n\ (1\le n\le 5000)$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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]\}$$$.

Example input:
2

Example output:
3 1

Example input:
3

Example output:
10 7 1

Editorial:
First we can make a bijection between all the good sequences and permutations. Let a permutation of length $$$n$$$ be $$$a_1,a_2,\cdots , a_n$$$ , and we fill '>' or '<' sign between each $$$a_i$$$ and $$$a_{i+1}$$$ , so the value of $$$p_{a_i}$$$ is the number of '<' sign between $$$a_1,a_2,\cdots, a_i$$$ plus one, it's easy to proof that this is a correct bijection.
Let $$$ d_{i,j}$$$ be the number of permutations of length $$$i+1$$$ that have at least $$$j$$$ '<' signs in it. Then for each '<' sign, we can combine the places next to it, so for some combined places, there are only one way to put the numbers in it for a fix set of numbers. And we know that $$$d_{i,j}$$$ have $$$i-j+1$$$ sets of combined places, so the value of $$$d_{i,j}$$$ is the number of ways to assign $$$i+1 $$$ numbers into $$$i-j+1$$$ different sets. From the EGF of the second kind of Stirling numbers, we know that $$$d_{i,j}=(i+1)![z^{i+1}](e^z-1)^{i-j+1}$$$ . We can also use DP that similar with the Stirling numbers to get all $$$d_{i,j}$$$ .
When we find the answers, for each $$$1\leq i\leq n$$$ , we consider the contribution of each places, so for each $$$a_j$$$ , we need to find the number of permutations that have $$$i-1$$$ '<' signs before it. So we can get:
$$$$$$ans_{i+1}=\sum\limits_{x=0}^{n-1}\sum\limits_{y=i}^x (-1)^{y-i} {y\choose i}d_{x,y}\frac{n!}{(x+1)!}$$$$$$ $$$$$$=\frac {n!}{i!}\sum\limits_{x=0}^{n-1}\sum\limits_{y=i}^x (-1)^{y-i}\frac{y!d_{x,y}}{(y-i)!(x+1)!} $$$$$$
$$$$$$=\frac{n!}{i!} \sum\limits_{y=i}^{n-1}\frac{(-1)^{y-i}y!}{(y-i)!}\sum\limits_{x=y}^{n-1}\frac{d_{x,y}}{(x+1)!}$$$$$$
$$$$$$=\frac {n!}{i!}\sum\limits_{y=i}^{n-1} \frac{(-1)^{y-i}y!}{(y-i)!} \sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1}$$$$$$
If we can find $$$\sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1}$$$ for each $$$y$$$ , then we can find the answer in one convolution.
And because of the simple $$$O(n^2)$$$ DP algorithm to find all $$$d_{x,y}$$$ , so we can get a $$$O(n^2)$$$ complexity to solve the problem, and it can pass the easy version (other forms of DP can also get to this time complexity, but now we only introduce the form that leads to the solution of the hard version).