Slime and Sequences (Hard Version)
Contest: Codeforces Round 641 (Div. 1)
Difficulty rating: 3500
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 100\,000)$$$.

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: 3.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:
Now we consider how to get these values in less than $$$O(n^2)$$$ time.
$$$$$$\sum\limits_{x=y}^{n-1}[z^{x+1}](e^z-1)^{x-y+1}=\sum\limits_{x=y+1}^n[z^x](e^z-1)^{x-y}$$$$$$
$$$$$$=[z^y]\sum\limits_{x=y+1}^n(\frac{e^z-1}z)^{x-y}=[z^y]\sum\limits_{x=1}^{n-y}(\frac{e^z-1}z)^x$$$$$$
Let $$$F=\frac{e^z-1}z$$$ , so now we just want to find $$$[z^i]\sum\limits_{k=1}^{n-i}F^k$$$ for each $$$0\leq i\leq n-1$$$ .
$$$$$$[z^i]\sum\limits_{k=1}^{n-i}F^k =[z^i]\frac 1{1-F}-[z^i]\frac{F^{n-i+1}}{1-F}$$$$$$
We can get the value of $$$[z^i]\frac 1{1-F}$$$ in one polynomial inversion, now we only need to deal with the second one.
$$$$$$[z^i]\frac{F^{n-i+1}}{1-F}=[z^{n+1}]\frac{(zF)^{n-i+1}}{1-F}$$$$$$
Let $$$w(z)=zF(z)$$$ , $$$\phi(z)$$$ satisfies $$$\frac{w(z)}{\phi (w(z))}=z$$$ , so $$$\frac{zF(z)}{\phi (w(z))}=z$$$ , $$$F=\phi (w)$$$ .
$$$$$$[z^{n+1}]\frac{(zF)^{n-i+1}}{1-F}=[z^{n+1}u^{n-i+1}]\sum\limits_{k=0}^\infty \frac{(uzF)^k}{1-F}$$$$$$
$$$$$$=[z^{n+1}u^{n-i+1}] \frac 1{1-\phi (w)}\frac 1{1-uw}$$$$$$
And from the Lagrange Inversion
$$$$$$=[u^{n-i+1}]\frac 1{n+1} [z^n] ((\frac 1{1-\phi z}\frac 1{1-uz})'\cdot \phi (z)^{n+1})$$$$$$
$$$$$$=\frac 1{n+1} [z^nu^{n-i+1}] (\phi (z)^{n+1}\frac{u+\phi'(z)-u\phi(z)-uz\phi'(z)}{(1-\phi (z))^2(1-uz)^2})$$$$$$
$$$$$$=\frac 1{n+1} [z^nu^{n-i+1}] (\phi(z)^{n+1}(\frac {u}{(1-\phi (z))(1-uz)^2}+\frac {\phi'(z)}{(1-\phi (z))^2(1-uz)}))$$$$$$
$$$$$$=\frac 1{n+1}[z^nu^{n-i+1}](\phi (z)^{n+1}(\frac 1{1-\phi(z)}\sum\limits_{k=0}^\infty (k+1)z^ku^{k+1}+\frac{\phi'(z)}{(1-\phi (z))^2}\sum\limits_{k=0}^\infty z^ku^k))$$$$$$
$$$$$$=\frac 1{n+1}[z^n](\phi (z)^{n+1}(\frac{(n-i+1)z^{n-i}}{1-\phi (z)}+\frac{\phi'(z)z^{n-i+1}}{(1-\phi(z))^2}))$$$$$$
$$$$$$=\frac 1{n+1}([z^i](\phi(z)^{n+1}\frac{n-i+1}{1-\phi(z)})+[z^{i-1}](\phi(z)^{n+1}\frac{\phi'(z)}{(1-\phi(z))^2}))$$$$$$
We can get $$$\phi(z)^{n+1}\frac{n-i+1}{1-\phi(z)}$$$ and $$$\phi(z)^{n+1}\frac{\phi'(z)}{(1-\phi(z))^2}$$$ in $$$O(n\log n)$$$ or $$$O(n\log ^2n)$$$ time, and then get the answer.
The overall complexity is $$$O(n\log n)$$$ or $$$O(n\log ^2n)$$$ .