D. DSU Master
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\)). 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\).