P7720 "EZEC-10" "Byakkai OI 2021" Estahv

> chrisl gjeztor Amledza > prof ovelmizer > dos carm ammeidha alzenghar > kawy may noxial gjeztor > Rupieilla vas photreywz idha

We have infinitely many cells in a row, numbered from left to right as $1,2,\dots$. You may fill any **positive integer** $k$ into each cell, and then you obtain the weight $C_k$. Here, $C_0=C_1=1$, and $C_i = \sum\limits_{j=0}^{i-1} C_j C_{i-j-1}$ $(i \ge 2)$. The total weight of several cells is defined as the product of their weights. Now you need to fill numbers into the cells from left to right, until the sum of the filled numbers becomes equal to $n$ or exceeds $n$. After that, you need to color each filled cell either black or white, satisfying: there do not exist any $2$ or more consecutive white cells, the first cell must be black, and the last filled cell must be white. Then, you need to add an edge between every pair of adjacent filled cells that have the same color, and select a set of cells $S$ such that any two cells in $S$ are not connected by an edge (it can be empty). The weight of a plan is defined as the total weight of all cells. Given $n$, for $s=0,1,\dots,n$, compute the sum of weights over all plans that complete all operations above, such that the sum of the filled numbers is **exactly** $n$, and the number of black cells is $s$. Two plans are different if and only if the number of filled cells is different, or the numbers filled in the corresponding cells are different, or the colors of the corresponding cells are different, or the set $S$ is different. Take the result modulo $998244353$.

The first line contains one positive integer $n$.

Output one line with $n+1$ non-negative integers, representing the answers for $s=0,1,\dots,n$.

[Explanation of Sample $1$.] When $n=3$, there can be $2$ or $3$ cells. If there are $2$ cells, the filling plans are $[1,2]$ or $[2,1]$, and the total weight is $2 \times C_1 \times C_2 = 4$; the coloring plan is `BW`, so there must be one black cell; the choices of the set $S$ are $\{\},\{1\},\{2\},\{1,2\}$ (cells are indexed by their numbers). If there are $3$ cells, the filling plan is $[1,1,1]$, and the weight is $C_1^3=1$; the coloring plan is `BBW`, so there must be two black cells; the choices of the set $S$ are $\{\},\{1\},\{2\},\{3\},\{1,3\},\{2,3\}$ (cells are indexed by their numbers). Here, `B` means black and `W` means white. [Constraints.] **This problem uses bundled tests.** - Subtask 1 (30 points): $n\le10$. - Subtask 2 (20 points): $n\le300$. - Subtask 3 (20 points): $n \le 5000$. - Subtask 4 (30 points): no special constraints, time limit is $3.5s$. For $100\%$ of the testdata, $1 \le n \le 10^5$. ### Hint To make it easier for everyone to get points with brute force, here is the result: $$ C_k = \frac1k \binom{2k}{k-1} = \binom{2k-1}{k-1}-\binom{2k-1}{k-2} $$ Translated by ChatGPT 5