Codeforces Round 858 (Div. 2) |
---|
Finished |
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:
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$$$.
$$$^\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$$$.
230 090 1 0 0 0 1 0 0
1 3 1 2 7 31 167 1002 7314 60612
Consider the first test case.
When $$$k=1$$$, there is only $$$1$$$ permutation $$$p$$$.
Therefore when $$$k=1$$$, the answer is $$$1$$$.
When $$$k=2$$$, there are $$$2$$$ permutations $$$p$$$.
Therefore when $$$k=2$$$, the answer is $$$2+1=3$$$.
Name |
---|