← 返回题目列表

Codeforces · 1806/D

D. DSU 主控

中文机器翻译题面 查看原题

给定一个整数 $$$n$$$ 和一个长度为 $$$n-1$$$ 的数组 $$$a$$$,其元素为 $$$0$$$ 或 $$$1$$$。

让我们通过以下过程定义长度为 $$$m-1$$$ ($$$m \leq n$$$) 的排列 $$$^\dagger$$$ $$$p$$$ 的值。

设 $$$G$$$ 为 $$$m$$$ 顶点的图,标记为从 $$$1$$$ 到 $$$m$$$,不包含任何边。对于从$$$1$$$到$$$m-1$$$的每个$$$i$$$,执行以下操作:

- 将 $$$u$$$ 和 $$$v$$$ 定义为弱连接组件 $$$^\ddagger$$$ 中的(唯一)顶点,分别包含顶点 $$$p_i$$$ 和 $$$p_i+1$$$ 且仅包含传入边$$$^{\dagger\dagger}$$$;
- 在图中 $$$G$$$ 中,如果 $$$a_{p_i}=0$$$,则添加从顶点 $$$v$$$ 到 $$$u$$$ 的有向边,否则添加从顶点 $$$u$$$ 到 $$$v$$$ 的有向边(如果 $$$a_{p_i}=1$$$)。

那么$$$p$$$的值为$$$G$$$的顶点$$$1$$$的入边数。

对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$k$$$,找到长度为 $$$k$$$ 的所有 $$$k!$$$ 排列的值之和。由于该值可能很大,因此您只需以 $$$998\,244\,353$$$ 为模计算该值。

$$$n=3$$$、$$$a=[0,1]$$$ 和 $$$p=[1,2]$$$ 时的运算

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$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$$$。