分数: 1600 点
问题陈述
Snuke 发现了一个随机数生成器。 它生成一个介于 0 和 2^N-1 (含)。 整数序列 A_0, A_1, \cdots, A_{2^N-1} 表示生成这些整数中的每一个的概率。整数 i (0 \leq i \leq 2^N-1) 是按概率生成的 A_i / S,其中 S = \sum_{i=0}^{2^N-1} A_i。每次执行生成器时,生成整数的过程都是独立完成的。
Snuke 有一个整数 X,现在是 0。 他可以多次执行以下操作:
- 生成一个整数 v 与发电机并更换 X 与 X \oplus v,其中 \oplus 表示按位异或。
对于每个整数 i (0 \leq i \leq 2^N-1),找到期望的操作数,直到 X 变为 i,并打印它的模数 998244353。 更正式地说,将预期操作数表示为不可约分数 P/Q。那么,存在唯一的整数 R 这样 R \times Q \equiv P \mod 998244353,\ 0 \leq R < 998244353,所以打印这个 R.
我们可以证明,对于每个 i,直到 X 变为 i 是一个有限有理数,其整数表示模 可以定义 998244353 。
约束
- 1 \leq N \leq 18
- 1 \leq A_i \leq 1000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0 A_1 \cdots A_{2^N-1}
输出
打印 2^N 行。 的 (i+1)第行(0 \leq i \leq 2^N-1)应包含预期的操作数,直到 X 变为 i,模数 998244353.
示例输入 1
2 1 1 1 1
示例输出 1
0 4 4 4
X=0 零次操作之后,因此预期的操作次数直到 X 变为 0 is 0.
另外,在任何状态下, X 一次操作后 0, 1, 2 or 3 具有相同的概率。 因此,直到 X 变为 1, 2 和 3 都是 4.
示例输入 2
2 1 2 1 2
示例输出 2
0 499122180 4 499122180
预计操作次数 X 变为 0, 1, 2 和 3 是 0, 7/2, 4 和 7/2。
示例输入 3
4 337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355
示例输出 3
0 468683018 635850749 96019779 657074071 24757563 745107950 665159588 551278361 143136064 557841197 185790407 988018173 247117461 129098626 789682908