CF1349F2.Slime and Sequences (Hard Version)

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 \gt 1$ that presents in $p$, there should be at least one pair of indices $i,j$, such that $1 \leq i \lt 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$$

注意：简单版本与困难版本的唯一区别在于对 $n$ 的约束以及时间限制。仅当两个版本均被解决时，才允许进行 Hack。

史莱姆对序列很感兴趣。他将长度为 $n$ 的“好”的正整数序列 $p$ 定义如下：

• 对于每个在 $p$ 中出现的 $k > 1$，都应至少存在一对下标 $i, j$，满足 $1 \leq i < j \leq n$，且 $p_i = k - 1$、$p_j = k$。

对于给定的整数 $n$，所有长度为 $n$ 的好序列构成的集合记为 $s_n$。对于固定的整数 $k$ 和序列 $p$，令 $f_p(k)$ 表示 $k$ 在 $p$ 中出现的次数。对于每个从 $1$ 到 $n$ 的 $k$，史莱姆希望计算以下值：

$$\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)$.

第一行包含一个整数 $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$.

输出 $n$ 个整数，其中第 $i$ 个整数应等于 $\left(\sum_{p\in s_n} f_p(i)\right)\ \textrm{mod}\ 998\,244\,353$。

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

在第一个例子中，$s={[1,1],[1,2]}$。

在第二个例子中，$s={[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]}$。

在第三个例子中，$s={[1]}$。