AT_abc283_g [ABC283G] Partial Xor Enumeration

题目描述

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$。

对于非负整数序列 $(a_1,a_2,\ldots,a_n)$，其 $\operatorname{xor}$ 定义为：存在一个整数 $X$，使得对于所有非负整数 $j$，满足以下条件：

• 当且仅当 $a_1,\ldots,a_n$ 中，用二进制表示时第 $2^j$ 位为 $1$ 的数的个数为奇数时，$X$ 的第 $2^j$ 位为 $1$。

设非负整数集合 $\lbrace s_1,s_2,\ldots,s_k\rbrace\ (s_1<s_2<\cdots<s_k)$ 为可以通过 $A$ 的（不一定连续，可以为空）子序列的 $\operatorname{xor}$ 得到的所有整数的集合。

给定整数 $L,R$，请按顺序输出 $s_L,s_{L+1},\ldots,s_R$。

输入格式

输入以以下格式从标准输入读入。

$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请按升序输出 $s_i\ (L\leq i\leq R)$，用空格分隔。

输入输出样例 #1

输入 #1

4 1 8
2 21 17 21

输出 #1

0 2 4 6 17 19 21 23

输入输出样例 #2

输入 #2

4 3 7
2 21 17 21

输出 #2

4 6 17 19 21

输入输出样例 #3

输入 #3

5 1 1
0 0 0 0 0

输出 #3

0

输入输出样例 #4

输入 #4

6 21 21
88 44 82 110 121 80

输出 #4

41

输入输出样例 #5

输入 #5

12 26 48
19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130

输出 #5

13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402

说明/提示

数据范围

• $1\leq N\leq2\times10^5$
• $0\leq A_i<2^{60}\ (1\leq i\leq N)$
• $1\leq L\leq R\leq k$
• $R-L\leq2\times10^5$
• 输入均为整数

样例解释 1

$A$ 的所有可能的（不一定连续）子序列有 $(),(2),(17),(21),(2,17),(2,21),(17,21),(21,17),(21,21),(2,17,21),(2,21,17),(2,21,21),(21,17,21),(2,21,17,21)$ 共 $14$ 种。它们的 $\operatorname{xor}$ 分别如下：

• 空序列的 $\operatorname{xor}$ 为 $0$。
• $(2)$ 的 $\operatorname{xor}$ 为 $2$。
• $(17)$ 的 $\operatorname{xor}$ 为 $17$。
• $(21)$ 的 $\operatorname{xor}$ 为 $21$。
• $(2,17)$ 的 $\operatorname{xor}$ 为 $19$。
• $(2,21)$ 的 $\operatorname{xor}$ 为 $23$。
• $(17,21)$ 的 $\operatorname{xor}$ 为 $4$。
• $(21,17)$ 的 $\operatorname{xor}$ 为 $4$。
• $(21,21)$ 的 $\operatorname{xor}$ 为 $0$。
• $(2,17,21)$ 的 $\operatorname{xor}$ 为 $6$。
• $(2,21,17)$ 的 $\operatorname{xor}$ 为 $6$。
• $(2,21,21)$ 的 $\operatorname{xor}$ 为 $2$。
• $(21,17,21)$ 的 $\operatorname{xor}$ 为 $17$。
• $(2,21,17,21)$ 的 $\operatorname{xor}$ 为 $19$。

因此，$A$ 的子序列的按位异或可能得到的值的集合为 $\lbrace0,2,4,6,17,19,21,23\rbrace$。

样例解释 5

请注意，输入或输出的数值可能超出 $32\operatorname{bit}$ 整数范围。

由 ChatGPT 4.1 翻译