← 返回题目列表

Codeforces · 1667/E

E. 质心概率

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

考虑每棵具有 $$$n$$$ 顶点的树(连通无向无环图)($$$n$$$ 为奇数,顶点编号从 $$$1$$$ 到 $$$n$$$),并且对于每个 $$$2 \le i \le n$$$,第 $$$i$$$ 个顶点恰好与索引较小的一个顶点相邻。

对于每个 $$$i$$$ ($$$1 \le i \le n$$$) 计算第 $$$i$$$ 个顶点作为质心的树的数量。答案可能很大,输出它对 $$$998\,244\,353$$$ 取模。

如果一个顶点的删除将树分割成每个最多包含 $$$(n-1)/2$$$ 个顶点的子树,则该顶点称为质心。

输入

第一行包含一个奇数整数 $$$n$$$ ($$$3 \le n < 2 \cdot 10^5$$$, $$$n$$$ 是奇数) — 树中顶点的数量。

输出

在一行中打印 $$$n$$$ 个整数,第 $$$i$$$ 个整数是第 $$$i$$$ 个顶点的答案(模 $$$998\,244\,353$$$)。

示例

输入 #1

3

输出 #1

1 1 0

输入 #2

5

输出 #2

10 10 4 0 0

输入 #3

7

输出 #3

276 276 132 36 0 0 0

注意

示例 $$$1$$$:有两种可能的树:边为 $$$(1-2)$$$ 和 $$$(1-3)$$$ — 这里的质心是 $$$1$$$;并且边为 $$$(1-2)$$$ 和 $$$(2-3)$$$ — 这里的质心是 $$$2$$$。所以答案是 $$$1, 1, 0$$$。

示例 $$$2$$$:有 $$$24$$$ 可能的树,例如边为 $$$(1-2)$$$、$$$(2-3)$$$、$$$(3-4)$$$ 和 $$$(4-5)$$$。这里的质心是$$$3$$$。