CF1101G (Zero XOR Subset)-less

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.

N/A

N/A

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