#P1349F2. Slime and Sequences (Hard Version)
Slime and Sequences (Hard Version)
No submission language available for this problem.
Description
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 100\,000)$.
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$.
Input
The first line contains one integer $n\ (1\le n\le 100\,000)$.
Output
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$.
Samples
2
3 1
3
10 7 1
1
1
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]\}$.