在数组中查找N个元素xor等于P.

Question

我正在研究一个问题,我期望N<20在XOR等于的数组中找到元素组合的数量P.

例如:我们的数组是{2 4 5 2 7}

1)如果N = 2且P = 6,

答案是2(因为我们只能选择(2 xor 4)= 6和(4 xor 2)= 6)

{ 2 4 5 2 7}或{2 4 5 2 7}

2)如果N = 3且P = 6

答案是1((4 x或5 x或7)= 6)

数组的大小可能非常大(大约10 ^ 6)所以我正在寻找快速算法来解决这个问题.

Answer 1

编辑不起作用，因为 N 是固定的

使用线性代数：

正如 @blazs 所建议的，您可以将 P 和数组中的每个数字视为 Z/2Z 向量空间中的向量。更重要的是，由于 XOR 是关联性和交换性的，因此您不是在寻找数组元素的组合，而是在寻找这些元素的集合，并且集合也可以编码为 Z/2Z 向量。

因此，您最终会得到像 M*S=P 这样的矩阵方程，其中 P 是 Z/2Z 向量格式的异或和，M 是矩阵，其中列是 Z/2Z 格式的数组元素，并且S 是方程的未知数。

由于您只对解空间的大小感兴趣，因此您所需要做的就是找到解空间的维数，然后计算 2 的幂。