← 返回题目列表

AtCoder · arc205_e

E. 子集产品问题

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

分数: 700 点

问题陈述

给你一个长度-N 非负整数序列 A=(A_1,A_2,\ldots,A_N).

对于 k=1,2,\ldots,N,解决以下问题。

  • 找到 产品,模数 998244353,属于 A_i 对于所有整数 i 之间 1 和 k,包含在内,这样按位 \mathrm{OR} 操作 A_i 和 A_k 等于 A_k.
什么是按位 \mathrm{OR} 操作?

按位 \mathrm{OR} 非负整数 X 和 Y,表示 X\ \mathrm{OR}\ Y定义如下。

  • 当 X\ \mathrm{OR}\ Y 以二进制形式写入,即 2^k (k \geq 0) 地点是 1 如果至少有一位数字位于 2^k 放置时 X 和 Y 写成二进制是 1,和 0 否则。
例如, 3\ \mathrm{OR}\ 5 = 7 (二进制: 011\ \mathrm{OR}\ 101 = 111).

约束

  • 1\le N\le 4\times 10^5
  • 0\le A_i < 2^{20}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

输出 N 行。

的 i第行 (1\le i\le N) 应包含案例的答案 k=i.


示例输入 1

4
1 2 3 5

示例输出 1

1
2
6
5
  • 当 k=1:对于 i=1,按位 \mathrm{OR} 操作 A_i 和 A_k is 1。因此,本案的答案 分别是 k=1 is A_1=1.
  • 当 k=2:对于 i=1,2,按位 \mathrm{OR} 操作 A_i 和 A_k is 3,2。因此,本案的答案 k=2 is A_2=2.
  • 当 k=3:对于 i=1,2,3,按位 \mathrm{OR} 操作 A_i 和 A_k 就是全部 3。因此,本案的答案 分别是 k=3 is A_1\times A_2\times A_3=6.
  • 当 k=4:对于 i=1,2,3,4,按位 \mathrm{OR} 操作 A_i 和 A_k is 5,7,7,5。因此,本案的答案 k=4 is A_1\times A_4=5.

示例输入 2

9
3 1 4 1 5 9 2 6 5

示例输出 2

3
1
4
1
20
9
2
48
100

示例输入 3

12
437926 528156 284664 1038330 692060 720863 602077 1027766 868190 532252 982711 876446

示例输出 3

437926
528156
284664
94842632
158208162
985930968
548875758
875494466
345599613
605424119
111381243
768586512