AT_abc197_c [ABC197C] ORXOR

题目描述

给定一个长度为 $N$ 的数列 $A$。
请将该数列划分为 $1$ 个或多个非空的连续区间。
然后，对每个区间内的数进行按位 $\mathrm{OR}$ 运算。
请你求出所有可能的划分方式中，得到的所有区间的按位 $\mathrm{OR}$ 结果再进行按位 $\mathrm{XOR}$ 运算后所得的最小值。

按位 $\mathrm{OR}$ 运算定义如下：
对于整数 $A, B$，其按位 $\mathrm{OR}$ 运算 $A\ \mathrm{OR}\ B$ 定义为：

• $A\ \mathrm{OR}\ B$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $A$ 或 $B$ 的该位至少有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3\ \mathrm{OR}\ 5 = 7$（二进制表示为：$011\ \mathrm{OR}\ 101 = 111$）。
一般地，$k$ 个整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{OR}$ 运算定义为 $((\dots((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\dots)\mathrm{OR}\ p_k)$，并且可以证明与顺序无关。

按位 $\mathrm{XOR}$ 运算定义如下：
对于整数 $A, B$，其按位 $\mathrm{XOR}$ 运算 $A\ \mathrm{XOR}\ B$ 定义为：

• $A\ \mathrm{XOR}\ B$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $A$ 和 $B$ 的该位恰好有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3\ \mathrm{XOR}\ 5 = 6$（二进制表示为：$011\ \mathrm{XOR}\ 101 = 110$）。
一般地，$k$ 个或更多整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{XOR}$ 运算定义为 $((\dots((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\dots)\mathrm{XOR}\ p_k)$，并且可以证明与顺序无关。

输入格式

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

$N$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 5 7

输出 #1

2

输入输出样例 #2

输入 #2

3
10 10 10

输出 #2

0

输入输出样例 #3

输入 #3

4
1 3 3 1

输出 #3

0

说明/提示

数据范围

• $1 \leq N \leq 20$
• $0 \leq A_i < 2^{30}$
• 输入中的所有值均为整数。

样例解释 1

将 $[1, 5, 7]$ 分成 $[1, 5]$ 和 $[7]$ 两个区间时，各区间内数的按位 $\mathrm{OR}$ 分别为 $5, 7$，它们的 $\mathrm{XOR}$ 为 $2$。无法得到更小的值，因此输出 $2$。

样例解释 2

可以分成 $[10]$ 和 $[10, 10]$。

样例解释 3

可以分成 $[1, 3]$ 和 $[3, 1]$。

由 ChatGPT 4.1 翻译