CF1806D.DSU Master

You are given an integer $n$ and an array $a$ of length $n-1$ whose elements are either $0$ or $1$ .

Let us define the value of a permutation $^\dagger$ $p$ of length $m-1$ ( $m \leq n$ ) by the following process.

Let $G$ be a graph of $m$ vertices labeled from $1$ to $m$ that does not contain any edges. For each $i$ from $1$ to $m-1$ , perform the following operations:

• define $u$ and $v$ as the (unique) vertices in the weakly connected components $^\ddagger$ containing vertices $p_i$ and $p_i+1$ respectively with only incoming edges $^{\dagger\dagger}$ ;
• in graph $G$ , add a directed edge from vertex $v$ to $u$ if $a_{p_i}=0$ , otherwise add a directed edge from vertex $u$ to $v$ (if $a_{p_i}=1$ ).

Note that after each step, it can be proven that each weakly connected component of $G$ has a unique vertex with only incoming edges.Then, the value of $p$ is the number of incoming edges of vertex $1$ of $G$ .

For each $k$ from $1$ to $n-1$ , find the sum of values of all $k!$ permutations of length $k$ . Since this value can be big, you are only required to compute this value under modulo $998\,244\,353$ .

Operations when $n=3$ , $a=[0,1]$ and $p=[1,2]$ $^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

$^\ddagger$ The weakly connected components of a directed graph is the same as the components of the undirected version of the graph. Formally, for directed graph $G$ , define a graph $H$ where for all edges $a \to b$ in $G$ , you add an undirected edge $a \leftrightarrow b$ in $H$ . Then the weakly connected components of $G$ are the components of $H$ .

$^{\dagger\dagger}$ Note that a vertex that has no edges is considered to have only incoming edges.

The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ( $2\le n\le 5 \cdot 10^5$ ).

The second line of each test case contains $n-1$ integers $a_1, a_2, \ldots, a_{n-1}$ ( $a_i$ is $0$ or $1$ ).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$ .

For each test case, output $n-1$ integers in a line, the $i$ -th integer should represent the answer when $k=i$ , under modulo $998\,244\,353$ .

Consider the first test case.

When $k=1$ , there is only $1$ permutation $p$ .

• When $p=[1]$ , we will add a single edge from vertex $2$ to $1$ . Vertex $1$ will have $1$ incoming edge. So the value of $[1]$ is $1$ .

Therefore when $k=1$ , the answer is $1$ .

When $k=2$ , there are $2$ permutations $p$ .

• When $p=[1,2]$ , we will add an edge from vertex $2$ to $1$ and an edge from $3$ to $1$ . Vertex $1$ will have $2$ incoming edges. So the value of $[1,2]$ is $2$ .
• When $p=[2,1]$ , we will add an edge from vertex $3$ to $2$ and an edge from $2$ to $1$ . Vertex $1$ will have $1$ incoming edge. So the value of $[2,1]$ is $1$ .

Therefore when $k=2$ , the answer is $2+1=3$ .