Centroid Probabilities
Contest: Codeforces Round 783 (Div. 1)
Difficulty rating: 3000
Tags: combinatorics, dp, fft, math

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.

Input format:
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.

Output format:
Print $$$n$$$ integers in a single line, the $$$i$$$-th integer is the answer for the $$$i$$$-th vertex (modulo $$$998\,244\,353$$$).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
3

Example output:
1 1 0

Example input:
5

Example output:
10 10 4 0 0

Editorial:
Let $$$S=\frac{n+1}{2}$$$, $$$binom_{i, j}=\frac{i!}{j! \cdot (i-j)!}$$$, $$$dp_i$$$ the result of some precalculation (see below) and $$$ans_i$$$ the final answer for the $$$i$$$-th vertex.
Root the tree in vertex $$$1$$$. It is easy to see that in the possible trees the parent of vertex $$$2≤i≤n$$$ is smaller than $$$i$$$. The cetroid will be the largest vertex, where the size of its subtree is at least $$$S$$$.
For each $$$i$$$ first calculate: how many times the subtree of vertex $$$i$$$ will be at least $$$S$$$ ($$$dp_i$$$).
If $$$i=1$$$, then $$$dp_i=(n-1)!$$$. If $$$i>S$$$ then the $$$dp_i=0$$$. Otherwise ($$$2≤i≤S$$$) $$$dp_i = \sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1)$$$
Proof: Let's assume that the size of the subtree is $$$j+1$$$. Color the subtree of vertex $$$i$$$ except $$$i$$$ red. Color every other vertex except the first and the $$$i$$$-th one to blue. We have $$$binom_{n-i, j}$$$ differnt colorings, because we have to choose $$$j$$$ values between $$$i+1$$$ and $$$n$$$. ($$$binom_{n-i, j}$$$)
There are $$$k$$$ possibilities for the parent of the $$$k$$$-th smallest blue or the $$$k$$$-th smallest red vertex. ($$$j! \cdot (n-j-2)!$$$)
The parent of the $$$i$$$-th vertex can be anything. ($$$i-1$$$)
If we multiply all of these, we get the described formula.
Then $$$ans_i=dp_i-\sum_{j=i+1}^{n} \frac{ans_j}{i}$$$
Proof: if the subtree of $$$i$$$ is at least $$$S$$$, and the centroid is not $$$i$$$, than the centroid is in the subtree of $$$i$$$. If $$$j$$$ is the centroid, there is exactly $$$\frac{1}{i}$$$ chance, that the path from $$$j$$$ to $$$1$$$ will cross vertex $$$i$$$. So we have to subract $$$\frac{ans_j}{i}$$$ for each $$$j>i$$$.
This gives us an $$$O(n^2)$$$ solution, which is slow because of the two sum formulas.
$$$\sum_{j=S-1}^{n-i} binom_{n-i, j} \cdot j! \cdot (n-j-2)! \cdot (i-1) = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot j! \cdot (n-j-1)! \cdot (i-1)}{j! \cdot (n-i-j)!} = \sum_{j=S-1}^{n-i} \frac {(n-i)! \cdot (n-j-2)! \cdot (i-1)}{(n-i-j)!}$$$
$$$(n-i)! \cdot (i-1)$$$ is a constant (for fixed $$$i$$$), and the difference between $$$n-j-2$$$ and $$$n-i-j$$$ is $$$i-2$$$, is also a constant for fixed $$$i$$$. If we reverse the inv array, then we can calculate $$$\sum_{j=S-1}^{n-i} \frac{(n-j-2)!}{(n-i-j)!}$$$ in $$$n \cdot log(n)$$$ time for $$$2≤i≤S$$$ with ntt.
We can do the calculation of $$$ans_i$$$ in linear time if we store the suffix sums of the latter values.
This gives us the final complexity: $$$O(n \cdot log(n))$$$.