102836: [Atcoder]ABC283 G - Partial Xor Enumeration
Description
Score : $600$ points
Problem Statement
For a sequence of non-negative integers $(a _ 1,a _ 2,\ldots,a _ n)$, let us define its $\operatorname{xor}$ as the integer $X$ such that, for all non-negative integer $j$:
- the $2^j$s place of $X$ is $1$ if and only if there is an odd number of elements among $a _ 1,\ldots,a _ n$ whose $2^j$s place is $1$.
You are given a sequence of non-negative integers $A=(A _ 1,A _ 2,\ldots,A _ N)$ of length $N$.
Let $\lbrace s _ 1,s _ 2,\ldots,s _ k\rbrace\ (s _ 1\lt s _ 2\lt\cdots\lt s _ k)$ be the set of all non-negative integers that can be the $\operatorname{xor}$ of a not-necessarily-contiguous (possibly empty) subsequence of $A$.
Given integers $L$ and $R$, print $s _ L,s _ {L+1},\ldots,s _ R$ in this order.
Constraints
- $1\leq N\leq2\times10^5$
- $0\leq A _ i\lt2^{60}\ (1\leq i\leq N)$
- $1\leq L\leq R\leq k$
- $R-L\leq2\times10^5$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $L$ $R$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$
Output
Print $s _ i\ (L\leq i\leq R)$ in ascending order of $i$, separated by spaces.
Sample Input 1
4 1 8 2 21 17 21
Sample Output 1
0 2 4 6 17 19 21 23
There are $14$ not-necessarily-contiguous subsequences of $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)$, and $(2,21,17,21)$, whose $\operatorname{xor}$s are as follows.
- The $\operatorname{xor}$ of $()$ is $0$.
- The $\operatorname{xor}$ of $(2)$ is $2$.
- The $\operatorname{xor}$ of $(17)$ is $17$.
- The $\operatorname{xor}$ of $(21)$ is $21$.
- The $\operatorname{xor}$ of $(2,17)$ is $19$.
- The $\operatorname{xor}$ of $(2,21)$ is $23$.
- The $\operatorname{xor}$ of $(17,21)$ is $4$.
- The $\operatorname{xor}$ of $(21,17)$ is $4$.
- The $\operatorname{xor}$ of $(21,21)$ is $0$.
- The $\operatorname{xor}$ of $(2,17,21)$ is $6$.
- The $\operatorname{xor}$ of $(2,21,17)$ is $6$.
- The $\operatorname{xor}$ of $(2,21,21)$ is $2$.
- The $\operatorname{xor}$ of $(21,17,21)$ is $17$.
- The $\operatorname{xor}$ of $(2,21,17,21)$ is $19$.
Therefore, the set of all non-negative integers that can be the $\operatorname{xor}$ of a subsequence of $A$ is $\lbrace0,2,4,6,17,19,21,23\rbrace$.
Sample Input 2
4 3 7 2 21 17 21
Sample Output 2
4 6 17 19 21
Sample Input 3
5 1 1 0 0 0 0 0
Sample Output 3
0
$A$ may contain the same value.
Sample Input 4
6 21 21 88 44 82 110 121 80
Sample Output 4
41
Sample Input 5
12 26 48 19629557415 14220078328 11340722069 30701452525 22333517481 720413777 11883028647 20926361028 24376768297 720413777 27999065315 13558621130
Sample Output 5
13558621130 14220078328 14586054825 15518998043 15970974282 16379590008 17091531049 17412316967 17836964726 18263536708 18965057557 19629557415 20282860278 20926361028 21302757781 21908867832 22333517481 22893781403 23595304394 23723463544 24376768297 24885524507 25261923402
Note that the input and output may not fit into a $32$-$\operatorname{bit}$ integer type.
Input
题意翻译
对于一个非负整数序列 $a = (a_1, a_2, \dots, a_n)$，我们定义其的异或是一个非负整数 $X$，使得对于任意非负整数 $j$ 有 $X$ 二进制的第 $j$ 位为 $1$ 当且仅当 $a$ 中有奇数个元素满足二进制的第 $j$ 位为 $1$。 给定一个 $n$ 长度序列 $A = (A_1, A_2, \dots, A_n)$。令 $\{s_1, s_2, \dots, s_k\}\ (s_1 < s_2 < \cdots < s_k)$ 为 $A$ 的所有可空子序列的异或组成的集合。注意子序列不一定连续。 再给定两个整数 $l, r$，请输出 $s_l, s_l + 1,\dots, s_r$。 $1\le n \le 2\times 10^5, \ 0\le A_i < 2^{60},\ 1\le l \le r \le k, \ r - l \le 2\times 10^5$。Output
问题描述
对于一个非负整数序列$(a_1, a_2, \ldots, a_n)$，我们定义它的$\operatorname{xor}$为一个整数$X$，使得对于所有的非负整数$j$：
- 当$X$的$2^j$位为$1$时，只有当$a_1, \ldots, a_n$中$2^j$位为$1$的元素个数为奇数时成立。
给你一个长度为$N$的非负整数序列$A = (A_1, A_2, \ldots, A_N)$。
记$\{s_1, s_2, \ldots, s_k\} \ (s_1 < s_2 < \cdots < s_k)$为所有可能的非负整数，这些整数可以是$A$的一个非连续子序列（可能为空）的$\operatorname{xor}$。
给定整数$L$和$R$，按照顺序输出$s_L, s_{L+1}, \ldots, s_R$。
约束
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 2^{60} \ (1 \leq i \leq N)$
- $1 \leq L \leq R \leq k$
- $R - L \leq 2 \times 10^5$
- 输入中的所有值均为整数。
输入
输入通过标准输入给出，格式如下：
$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
按照递增顺序输出$i$（$L \leq i \leq R$）的$s_i$，每个数字之间用空格分隔。
样例输入 1
4 1 8 2 21 17 21
样例输出 1
0 2 4 6 17 19 21 23
对于序列$A$，有$14$个可能的非连续子序列：$(), (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)$，它们的$\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$的所有非负整数子序列的$\operatorname{xor}$集合为$\{0, 2, 4, 6, 17, 19, 21, 23\}$。
样例输入 2
4 3 7 2 21 17 21
样例输出 2
4 6 17 19 21
样例输入 3
5 1 1 0 0 0 0 0
样例输出 3
0
序列$A$可能包含相同的值。
样例输入 4
6 21 21 88 44 82 110 121 80
样例输出 4
41
样例输入 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
注意，输入和输出可能不适合放在一个$32$-$\operatorname{bit}$整