← 返回题目列表

Codeforces · 1349/F2

F2. 史莱姆和序列(硬版)

中文机器翻译题面 查看原题

请注意,简单版和困难版之间的唯一区别是 $$$n$$$ 的约束和时间限制。只有解决了所有版本才可以进行黑客攻击。

史莱姆对序列感兴趣。他定义了长度为 $$$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$$$,Slime 想知道以下值:

$$$$$$\left(\sum_{p\in s_n} f_p(k)\right)\ \textrm{mod}\ 998\,244\,353$$$$$$

输入

第一行包含一个整数$$$n\ (1\le n\le 100\,000)$$$。

输出

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

示例

输入 #1

2

输出 #1

3 1

输入 #2

3

输出 #2

10 7 1

输入 #3

1

输出 #3

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]\}$$$。