← 返回题目列表

AtCoder · utpc2022_m

M. 通过重新分配最小化异或

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

配点 : 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