Slime and Sequences (Hard Version)

题意翻译

对于正整数序列 $p$，定义 $p$ 是好的，当且仅当如果 $k$ 在 $p$ 中出现过，那么在 $k$ 的最后一次出现之前，有 $k-1$ 出现过。 设所有长度为 $n$ 的好的序列组成的集合为 $S_n$。对于序列 $p$ 和正整数 $i$ 定义 $f_p(i)$ 为 $i$ 在 $p$ 中出现的次数。现在请你对于所有 $i \in [1,n]$，求出 $$\sum_{p \in S_n} f_p(i)$$ 对 $998\ 244\ 353$ 取模的结果。 $n\le 10^5$ _Translated by Caro23333_

题目描述

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

输入输出样例

输入样例 #1

2

输出样例 #1

3 1

输入样例 #2

3

输出样例 #2

10 7 1

输入样例 #3

1

输出样例 #3

1

说明

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

题意翻译

对于正整数序列 $p$，定义 $p$ 是好的，当且仅当如果 $k$ 在 $p$ 中出现过，那么在 $k$ 的最后一次出现之前，有 $k-1$ 出现过。 设所有长度为 $n$ 的好的序列组成的集合为 $S_n$。对于序列 $p$ 和正整数 $i$ 定义 $f_p(i)$ 为 $i$ 在 $p$ 中出现的次数。现在请你对于所有 $i \in [1,n]$，求出 $$\sum_{p \in S_n} f_p(i)$$ 对 $998\ 244\ 353$ 取模的结果。 $n\le 10^5$ _Translated by Caro23333_