← 返回题目列表

Codeforces · 1101/G

G. (零异或子集)-less

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

给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$。

您的任务是将数组划分为最大数量的段,方式如下:

- 每个元素恰好包含在一个段中;
- 每个段至少包含一个元素;
- 不存在段的非空子集,使得它们中的数字的按位异或等于 $$$0$$$。

打印数组可以分为的最大段数。如果不存在合适的划分,则打印 -1。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

输出

打印在遵循给定约束的情况下数组可以分为的最大段数。如果不存在合适的划分,则打印 -1。

示例

输入 #1

4
5 5 7 2

输出 #1

2

输入 #2

3
1 2 3

输出 #2

-1

输入 #3

3
3 1 10

输出 #3

3

注意

在第一个示例中,$$$2$$$ 是最大数量。如果将数组分为$$$\{[5], [5, 7, 2]\}$$$,则仅第二段的子集的异或值为$$$5 \oplus 7 \oplus 2 = 0$$$。 $$$\{[5, 5], [7, 2]\}$$$ 仅第一段的子集值为 $$$5 \oplus 5 = 0$$$。然而,$$$\{[5, 5, 7], [2]\}$$$ 将导致 XOR $$$7$$$ 的子集 $$$\{[5, 5, 7]\}$$$,XOR $$$2$$$ 的 $$$\{[2]\}$$$ 和 XOR $$$5 \oplus 的 $$$\{[5, 5, 7], [2]\}$$$ 5 \oplus 7 \oplus 2 = 5$$$。

让我们看一下 $$$3$$$ 段上的一些划分 — $$$\{[5], [5, 7], [2]\}$$$。它将产生子集:

- $$$\{[5]\}$$$,异或 $$$5$$$;
- $$$\{[5, 7]\}$$$,异或 $$$2$$$;
- $$$\{[5], [5, 7]\}$$$, 异或 $$$7$$$;
- $$$\{[2]\}$$$,异或$$$2$$$;
- $$$\{[5], [2]\}$$$, 异或 $$$7$$$;
- $$$\{[5, 7], [2]\}$$$, 异或 $$$0$$$;
- $$$\{[5], [5, 7], [2]\}$$$, 异或 $$$5$$$;

如您所见,子集 $$$\{[5, 7], [2]\}$$$ 的异或等于 $$$0$$$,这是不可接受的。您可以检查对于大小 $$$3$$$ 或 $$$4$$$ 的其他划分,与 $$$0$$$ XOR 的非空子集始终存在。

第二个示例没有合适的划分。

第三个示例数组可以分为$$$\{[3], [1], [10]\}$$$。这些段的子集的 XOR 都不等于 $$$0$$$。