最小长度子数组，使其具有异或和为 0 的子序列

Question

我被一个竞争性编程档案中的这个问题困住了，它说：

Given an array of integers A of length n, we need to find the minimum length
subarray such that it has a subsequence with an xor sum of 0. (Subarray is a
contiguous segment of an array and subsequence is a sequence that can be
derived from a subarray by deleting zero or more elements.) The resulting
subarray must have a length of at least 1. (Empty subarray cannot be an answer.)

1 <= n <= 10^5
1 <= A[i] <= 10^9

由于限制很大，典型的动态规划方法似乎不起作用。我读过有关高斯消元法 2 的内容，但我不知道它如何适用于这个问题。由于该方程组可能有指数数量的解，因此选择最小长度子数组应该不那么容易。我也考虑过采用滑动窗口方法，但我不知道如何支持将下一个数字添加到我们的数据结构中并删除第一个数字。类似于子集和问题的位集方法也不会起作用，因为数字最多为 10^9 并且我们无法使用那么多内存。

这些都是我试图解决这个问题的所有方法。欢迎任何想法和资源。如果有适合此任务的有效算法，请告诉我。

Answer 1

取任意长度为 30 的子数组。每个 A[i] < 2 ³⁰，所以有两种可能性：

1. 这 30 个整数是线性（通过异或）独立的，在这种情况下，您可以通过将适当的子序列异或在一起来生成任何30 位整数，包括数组中的下一个整数；或者
2. 这 30 个整数不是线性独立的，在这种情况下，您可以通过将适当的非空子序列异或在一起来得到 0。

在任何一种情况下，子数组加上下一个元素都会有一个异或为 0 的子序列。因此，具有此类子序列的最小子数组的长度始终 <= 31，除非数组很短且根本没有此类子序列。

^{在 N < 10 5}的约束下，您有足够的时间对长度 < 31 的每个子数组尝试高斯消除。

请记住：您实际上不必找到异或为零的子序列。只需要使用高斯消去法看看子数组中的整数是否线性无关。

下面是 python 中的一个示例实现（为了清楚起见，尽管 python 很慢）：

def smallestSubarrayLength(A):
    rows = [0]*32
    bestLength = None

    # add rows starting at start to a Gaussian elimination
    for start in range(len(A)):
        n=1
        rows[0] = A[start]
        for i in range(1,min(32,len(A)-start)):
            newrow = A[start+i]
            for j in range(n):
                # rows will be in descending order,
                # and each entry will have a different high bit
                oldrow = rows[j]
                if (newrow > oldrow):
                    rows[j] = newrow
                    newrow = min(oldrow, newrow ^ oldrow)
                else:
                    newrow = min(newrow, newrow ^ oldrow)
            rows[n] = newrow
            n += 1
            if newrow == 0:
                # The rows are not linearly independent
                if bestLength == None or n < bestLength:
                    bestLength = n
                break
    return bestLength