E - Subset Product Problem Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

k=1,2,\ldots,N に対し以下の問題を解いてください。

  • A_i と A_k のビット単位 \mathrm{OR} 演算が A_k となるような 1 以上 k 以下の整数 i 全てに対する A_i の 総積 を 998244353 で割ったあまりを求めてください。
ビット単位 \mathrm{OR} 演算とは

非負整数 X,Y のビット単位 \mathrm{OR}、X\ \mathrm{OR}\ Y は以下のように定義されます。

  • X\ \mathrm{OR}\ Y を二進表記した際の 2^k (k \geq 0) の位の数は、X,Y を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 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 に対し A_i と A_k のビット単位 \mathrm{OR} 演算は 1 になります。したがって、 k=1 の場合の答えは A_1=1 です。
  • k=2 のとき： i=1,2 に対し A_i と A_k のビット単位 \mathrm{OR} 演算はそれぞれ 3,2 になります。したがって、 k=2 の場合の答えは A_2=2 です。
  • k=3 のとき： i=1,2,3 に対し A_i と A_k のビット単位 \mathrm{OR} 演算は全て 3 になります。したがって、 k=3 の場合の答えは A_1\times A_2\times A_3=6 です。
  • k=4 のとき： i=1,2,3,4 に対し A_i と A_k のビット単位 \mathrm{OR} 演算はそれぞれ 5,7,7,5 になります。したがって、 k=4 の場合の答えは 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

Score : 700 points

Problem Statement

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\ldots,A_N).

For k=1,2,\ldots,N, solve the following problem.

  • Find the product, modulo 998244353, of A_i for all integers i between 1 and k, inclusive, such that the bitwise \mathrm{OR} operation of A_i and A_k equals A_k.
What is bitwise \mathrm{OR} operation?

The bitwise \mathrm{OR} of non-negative integers X and Y, denoted X\ \mathrm{OR}\ Y, is defined as follows.

  • When X\ \mathrm{OR}\ Y is written in binary, the digit at the 2^k (k \geq 0) place is 1 if at least one of the digits at the 2^k place when X and Y are written in binary is 1, and 0 otherwise.
For example, 3\ \mathrm{OR}\ 5 = 7 (in binary: 011\ \mathrm{OR}\ 101 = 111).

Constraints

  • 1\le N\le 4\times 10^5
  • 0\le A_i < 2^{20}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Output N lines.

The i-th line (1\le i\le N) should contain the answer for the case k=i.

Sample Input 1

4
1 2 3 5

Sample Output 1

1
2
6
5
  • When k=1: For i=1, the bitwise \mathrm{OR} operation of A_i and A_k is 1. Therefore, the answer for the case k=1 is A_1=1.
  • When k=2: For i=1,2, the bitwise \mathrm{OR} operation of A_i and A_k is 3,2, respectively. Therefore, the answer for the case k=2 is A_2=2.
  • When k=3: For i=1,2,3, the bitwise \mathrm{OR} operation of A_i and A_k is all 3. Therefore, the answer for the case k=3 is A_1\times A_2\times A_3=6.
  • When k=4: For i=1,2,3,4, the bitwise \mathrm{OR} operation of A_i and A_k is 5,7,7,5, respectively. Therefore, the answer for the case k=4 is A_1\times A_4=5.

Sample Input 2

9
3 1 4 1 5 9 2 6 5

Sample Output 2

3
1
4
1
20
9
2
48
100

Sample Input 3

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

Sample Output 3

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