309360: CF1667E. Centroid Probabilities

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Centroid Probabilities

题意翻译

对于所有点数为 $n$ 的树,如果其满足 对于所有 $i\in [2,n]$,与 $i$ 相连的 $j$ 中有且只有一个点 $j$ 满足 $j<i$ ,那么我们称其为好树 对于 $1\sim n$ 每个点求出来有多少好树满足重心为 $i$ 这里重心定义为删去这个点后形成的所有连通块大小均小于 $\frac{n-1}2$ 数据范围 $3\le n\le 2\times 10^5$ 且 $n$ 为奇数(所以不存在树有多个重心的情况)

题目描述

Consider every tree (connected undirected acyclic graph) with $ n $ vertices ( $ n $ is odd, vertices numbered from $ 1 $ to $ n $ ), and for each $ 2 \le i \le n $ the $ i $ -th vertex is adjacent to exactly one vertex with a smaller index. For each $ i $ ( $ 1 \le i \le n $ ) calculate the number of trees for which the $ i $ -th vertex will be the centroid. The answer can be huge, output it modulo $ 998\,244\,353 $ . A vertex is called a centroid if its removal splits the tree into subtrees with at most $ (n-1)/2 $ vertices each.

输入输出格式

输入格式


The first line contains an odd integer $ n $ ( $ 3 \le n < 2 \cdot 10^5 $ , $ n $ is odd) — the number of the vertices in the tree.

输出格式


Print $ n $ integers in a single line, the $ i $ -th integer is the answer for the $ i $ -th vertex (modulo $ 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

说明

Example $ 1 $ : there are two possible trees: with edges $ (1-2) $ , and $ (1-3) $ — here the centroid is $ 1 $ ; and with edges $ (1-2) $ , and $ (2-3) $ — here the centroid is $ 2 $ . So the answer is $ 1, 1, 0 $ . Example $ 2 $ : there are $ 24 $ possible trees, for example with edges $ (1-2) $ , $ (2-3) $ , $ (3-4) $ , and $ (4-5) $ . Here the centroid is $ 3 $ .

Input

题意翻译

对于所有点数为 $n$ 的树,如果其满足 对于所有 $i\in [2,n]$,与 $i$ 相连的 $j$ 中有且只有一个点 $j$ 满足 $j<i$ ,那么我们称其为好树。 对于 $1\sim n$ 每个点求出来有多少好树满足重心为 $i$。 这里重心定义为删去这个点后形成的所有连通块大小均不超过 $\frac{n-1}2$。 数据范围 $3\le n\le 2\times 10^5$ 且 $n$ 为奇数(所以不存在树有多个重心的情况)。

加入题单

上一题 下一题 算法标签: