DSU Master
Contest: Codeforces Round 858 (Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, dsu, math

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$$$).

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.

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

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

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

Example input:
2
3
0 0
9
0 1 0 0 0 1 0 0

Example output:
1 3 
1 2 7 31 167 1002 7314 60612

Editorial:
We record an operation of adding edge as $$$(i,i+1,a_i)$$$.
Hint 1: Only operation $$$(i,i+1,0)$$$ can contribute.
Hint 2: Using dynamic programming, let $$$f_i$$$ denote the number of ways to let vertices $$$1\sim i$$$ form a tree with root $$$1$$$, considering only the first $$$i-1$$$ operations.
We can observe:
• Only operation $$$(i,i+1,0)$$$ can contribute.
• If vertices $$$1\sim i$$$ have already formed a tree with root $$$1$$$, then operation $$$(i,i+1,0)$$$ can contribute.
Using dynamic programming, let $$$f_i$$$ denote the number of ways to let vertices $$$1\sim i$$$ form a tree with root $$$1$$$, considering only the first $$$i-1$$$ operations.
For $$$f$$$, we have $$$f_1=1$$$ and $$$f_{i+1}=f_i\cdot (i-a_i)$$$.
Explanation: Consider inserting the operation $$$(i,i+1,a_i)$$$ in the sequence of the first $$$i-1$$$ operations. If $$$a_i=0$$$, no matter where it is inserted, it will always form a tree with root $$$1$$$, so $$$f_{i+1}=f_i\cdot i$$$. If $$$a_i=1$$$, only inserting at the end is invalid, so $$$f_{i+1}=f_i\cdot (i-1)$$$. This is because, if you insert $$$(i,i+1,1)$$$ at the end of the operations, we will add a edge from $$$1$$$ to $$$i+1$$$, which won't form a tree of root $$$1$$$.
For computing the answer, we have $$$ans_i=i\cdot ans_{i-1}+[a_i=0]f_{i}$$$.
Explanation: $$$i\cdot ans_{i-1}$$$ represents the contribution of previous $$$i-1$$$ operations. No matter where operation $$$(i,i+1,a_i)$$$ is inserted, the contribution of previous $$$i-1$$$ operations won't change. $$$[a_i=0]f_{i}$$$ means the contribution of operation $$$(i,i+1,a_i)$$$.