XOR Sequence Partition
Given a sequence of N integers A_1, A_2, ..., A_N, partition it into the minimum number of contiguous subsequences such that the XOR sum of each subsequence is non-zero. Print the minimum number of subsequences.
Input
The first line contains an integer N. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer, the minimum number of subsequences.
Constraints
1 <= N <= 200000, 0 <= A_i <= 10^9
Example 1
6 1 2 3 1 2 3
3
The algorithm yields 3 partitions. The splits occur when the XOR sum of the current partition segment becomes 0. For [1, 2, 3, 1, 2, 3]: 1. Partition 1 starts. Elements [1, 2]. XOR sum = 3. `seen_prefix_xors` = {0, 1, 3}. 2. Element 3 is added. Current XOR sum (from start of partition) becomes 3^3 =
Example 2
5 0 0 0 0 0
6
Each '0' element, when XORed with the previous state, will result in '0'. Since '0' is always in `seen_prefix_xors` initially, each '0' forces a new partition (except the very first element if it's '0'). Trace: N=5, A=[0,0,0,0,0] 1. partitions=1, cx=0, ss={0}. 2. i=0, A[0]=0: cx=0^0=0. 0 in ss. part
Example 3
1 100
1
A single element always forms one partition if its value is non-zero. If N=1, A=[100]. init: p=1, cx=0, ss={0}. i=0, A[0]=100: cx=100. 100 not in ss. ss={0,100}. Final p=1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 1 2 3 1 2 3
5 0 0 0 0 0
1 100