CF1101G (Zero XOR Subset)-less

题意简述 给出一个序列$\{a_i\}$，试将其划分为尽可能多的非空子段，满足每一个元素出现且仅出现在其中一个子段中，且在这些子段中任取若干子段，它们包含的所有数的异或和不能为$0$．

无

无

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