DSU Master

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个整数 $n$ 和一个长度为 $n-1$ 的数组 $a$，其中每个元素都是 $0$ 或 $1$。

我们定义一个长度为 $m-1$（$m \leq n$）的排列 $p$ 的值如下：

令 $G$ 为一个有 $m$ 个顶点的图，顶点编号为 $1$ 到 $m$，初始时没有任何边。对于每个 $i$ 从 $1$ 到 $m-1$，执行以下操作：

• 设 $u$ 和 $v$ 分别为包含顶点 $p_i$ 和 $p_i+1$ 的弱连通分量中仅有入边的（唯一）顶点；
• 如果 $a_{p_i}=0$，则在图 $G$ 中添加一条从顶点 $v$ 指向 $u$ 的有向边；否则（即 $a_{p_i}=1$），添加一条从 $u$ 指向 $v$ 的有向边。

注意，每一步操作后，可以证明 $G$ 的每个弱连通分量都恰好有一个仅有入边的顶点。排列 $p$ 的值定义为 $G$ 中顶点 $1$ 的入边数。

对于每个 $k$ 从 $1$ 到 $n-1$，求所有长度为 $k$ 的排列的值之和（共 $k!$ 个排列）。由于答案可能很大，只需输出对 $998\,244\,353$ 取模的结果。

当 $n=3$，$a=[0,1]$ 且 $p=[1,2]$ 时的操作示意图。

$^\dagger$ 长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 的所有整数且顺序任意的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但数组中有 $4$）。

$^\ddagger$ 有向图的弱连通分量与其无向版本的连通分量相同。形式化地，对于有向图 $G$，定义图 $H$，对于 $G$ 中的每条边 $a \to b$，在 $H$ 中添加一条无向边 $a \leftrightarrow b$。则 $G$ 的弱连通分量即为 $H$ 的连通分量。

$^{\dagger\dagger}$ 注意，没有任何边的顶点也被认为是仅有入边的顶点。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 5 \cdot 10^5$）。

第二行包含 $n-1$ 个整数 $a_1, a_2, \ldots, a_{n-1}$（$a_i$ 为 $0$ 或 $1$）。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 $n-1$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案，对 $998\,244\,353$ 取模。

样例输入 1

2
3
0 0
9
0 1 0 0 0 1 0 0

样例输出 1

1 3 
1 2 7 31 167 1002 7314 60612

提示

考虑第一个测试用例。

当 $k=1$ 时，只有 $1$ 个排列 $p$。

• 当 $p=[1]$ 时，会添加一条从顶点 $2$ 指向 $1$ 的边。顶点 $1$ 有 $1$ 条入边，所以 $[1]$ 的值为 $1$。

因此当 $k=1$ 时，答案为 $1$。

当 $k=2$ 时，有 $2$ 个排列 $p$。

• 当 $p=[1,2]$ 时，会添加一条从顶点 $2$ 指向 $1$ 的边，再添加一条从 $3$ 指向 $1$ 的边。顶点 $1$ 有 $2$ 条入边，所以 $[1,2]$ 的值为 $2$。
• 当 $p=[2,1]$ 时，会添加一条从 $3$ 指向 $2$ 的边，再添加一条从 $2$ 指向 $1$ 的边。顶点 $1$ 有 $1$ 条入边，所以 $[2,1]$ 的值为 $1$。

因此当 $k=2$ 时，答案为 $2+1=3$。

数据范围

对所有数据，$1\le t\le 10^4$，$2\le n\le 5\times 10^5$，$a_i\in\{0,1\}$，且同一输入文件中所有测试用例的 $n$ 之和不超过 $5\times 10^5$。

各子任务的测试点独立计分。