(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 $ .