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