CF1806D DSU Master

给定一个整数 $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$ 取模。

考虑第一个测试用例。 当 $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$。 由 ChatGPT 4.1 翻译