分数: 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 否则。
约束
- 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