(Zero XOR Subset)-less

题意翻译

题意简述 给出一个序列$\{a_i\}$，试将其划分为尽可能多的非空子段，满足每一个元素出现且仅出现在其中一个子段中，且在这些子段中任取若干子段，它们包含的所有数的异或和不能为$0$． 输入格式 第一行一个整数$n(1 \leq n \leq 2*10^5)$表示序列长度 接下来一行$n$个整数$a_i(0 \leq a_i \leq 10^9)$描述这个序列 输出格式 一行，如果不存在方案输出`-1`，否则输出所有合法的划分方案中最大的划分数

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ of integer numbers. Your task is to divide the array into the maximum number of segments in such a way that: - each element is contained in exactly one segment; - each segment contains at least one element; - there doesn't exist a non-empty subset of segments such that bitwise XOR of the numbers from them is equal to $ 0 $ . Print the maximum number of segments the array can be divided into. Print -1 if no suitable division exists.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of the array. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 10^9 $ ).

输出格式

Print the maximum number of segments the array can be divided into while following the given constraints. Print -1 if no suitable division exists.

输入输出样例

输入样例 #1

4
5 5 7 2

输出样例 #1

2

输入样例 #2

3
1 2 3

输出样例 #2

-1

输入样例 #3

3
3 1 10

输出样例 #3

3

说明

In the first example $ 2 $ is the maximum number. If you divide the array into $ \{[5], [5, 7, 2]\} $ , the XOR value of the subset of only the second segment is $ 5 \oplus 7 \oplus 2 = 0 $ . $ \{[5, 5], [7, 2]\} $ has the value of the subset of only the first segment being $ 5 \oplus 5 = 0 $ . However, $ \{[5, 5, 7], [2]\} $ will lead to subsets $ \{[5, 5, 7]\} $ of XOR $ 7 $ , $ \{[2]\} $ of XOR $ 2 $ and $ \{[5, 5, 7], [2]\} $ of XOR $ 5 \oplus 5 \oplus 7 \oplus 2 = 5 $ . Let's take a look at some division on $ 3 $ segments — $ \{[5], [5, 7], [2]\} $ . It will produce subsets: - $ \{[5]\} $ , XOR $ 5 $ ; - $ \{[5, 7]\} $ , XOR $ 2 $ ; - $ \{[5], [5, 7]\} $ , XOR $ 7 $ ; - $ \{[2]\} $ , XOR $ 2 $ ; - $ \{[5], [2]\} $ , XOR $ 7 $ ; - $ \{[5, 7], [2]\} $ , XOR $ 0 $ ; - $ \{[5], [5, 7], [2]\} $ , XOR $ 5 $ ; As you can see, subset $ \{[5, 7], [2]\} $ has its XOR equal to $ 0 $ , which is unacceptable. You can check that for other divisions of size $ 3 $ or $ 4 $ , non-empty subset with $ 0 $ XOR always exists. The second example has no suitable divisions. The third example array can be divided into $ \{[3], [1], [10]\} $ . No subset of these segments has its XOR equal to $ 0 $ .

题意翻译

题意简述 给出一个序列$\{a_i\}$，试将其划分为尽可能多的非空子段，满足每一个元素出现且仅出现在其中一个子段中，且在这些子段中任取若干子段，它们包含的所有数的异或和不能为$0$． 输入格式 第一行一个整数$n(1 \leq n \leq 2*10^5)$表示序列长度 接下来一行$n$个整数$a_i(0 \leq a_i \leq 10^9)$描述这个序列 输出格式 一行，如果不存在方案输出`-1`，否则输出所有合法的划分方案中最大的划分数