M - Minimize XOR by Redistribution Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ n の非負整数列 X=(X_1,X_2,\dots,X_n) に対し f(X) を、Y_1+Y_2+\dots+Y_n=X_1+X_2+\dots+X_n を満たす長さ n の非負整数列 Y=(Y_1,Y_2,\dots,Y_n) 全てにおける Y_1 \oplus Y_2 \oplus \dots \oplus Y_n の最小値とします。ただしここで、\oplus はビット単位 \mathrm{XOR} 演算を表します。

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。 A の空でない部分列 B は 2^N-1 個考えられますが、それらすべてに対する f(B) の総和を 998244353 で割ったあまりを求めてください。

ビット単位 \mathrm{XOR} 演算とは

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

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 入力は全て整数
  • 1 \leq N \leq 2000
  • 0 \leq A_i < 2^{20}

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを 1 行に出力せよ。

入力例 1

3
0 1 2

出力例 1

8

A の空でない 部分列 B は B=(0),(1),(2),(0,1),(0,2),(1,2),(0,1,2) の 7 個存在します。

例えば B=(0,2) のとき、1+1=0+2,\ 1 \oplus 1 = 0 であるため f(B)=0 です。

上記の 7 個の A の部分列に対する f(B) は順に 0,1,2,1,0,3,1 となるため、答えは 0+1+2+1+0+3+1=8 となります。

入力例 2

15
99412 355422 750910 993699 41414 435678 325371 637849 939332 512546 112254 175315 865362 459658 311661

出力例 2

7032514