← 返回题目列表

AtCoder · agc034_f

F. RNG 和异或

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

分数: 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