← 返回题目列表

AtCoder · awtf2025_d

D. BFS 有序树

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

分数: 1400 点

问题陈述

给你一个整数 N。 我们称一棵有根的树 T 满足以下条件a BFS 有序树.

  • T 是一棵有根树 N 顶点编号自 1 to N.
  • 根是顶点 1.
  • 让顶点 p_i 是每个顶点的父顶点 i (2 \leq i \leq N)。然后, p_2 \leq p_3 \leq \cdots \leq p_N 成立。

对于每个 d=1,2,\ldots,(N-1),求模数 998244353,BFS 有序树 T 满足以下条件。

  • 顶点之间的距离 (N-1) 和 N in T 正是 d。 更准确地说,当考虑 T 作为无向树和连接顶点的路径 (N-1) 和 N,该路径中的边数恰好是 d.

约束

  • 2 \leq N \leq 10^6
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N

输出

输出 N-1 行。 的 i- 第行应包含以下问题的答案 d=i.


示例输入 1

2

示例输出 1

1

示例输入 2

3

示例输出 2

1
1

示例输入 3

4

示例输出 3

2
2
1

示例输入 4

5

示例输出 4

5
5
3
1

示例输入 5

20

示例输出 5

477638700
477638700
178405156
178405139
109639972
108787985
86366256
69212603
43976909
22930595
9698374
3355343
947052
215710
38814
5324
524
33
1