请教一个算法题-是否存在所有元素异或结果为 0 的子数组

[sdushn]

• 给定一个 int 型的 M 和 N，其中 M 小于等于 340，N 小于等于 50000 ；
• 给出一个 int[N]数组，数组中每个数都小于 2 的 M 次方；
• 问题：是否存在一个子数组，使得子数组中所有元素异或后的结果为 0 ？存在输出 yes，不存在输出 no。要求子数组元素之和大于 0。
• 例子：M=7，N=5，int[] input = {0, 1, 2, 3, 5}；存在子序列{1, 2, 3}，1 ^ 2 ^ 3 = 0，所以输出 yes。
  M=7，N=5，int[] input = {0, 1, 3, 5, 9}；不存在这样的子序列，输出 no。
• 我的思路：最初结题的思路是迭代求最小异或值（排除 0 元素），但是发现和数组的顺序是相关的，后面想到，如果都写成二进制，排成 N 行 M 列的矩阵，如果某一列相加的值为 1，证明只有一个元素在该位为 1，是绝对不会出现在最终的子序列中的，这样可以排除掉一部分，如果出现例如{5, 7, 4, 3}这样的数据就不知道该怎么样做比较好了。
• 拓展：如果问题升级，输出存在几个这样的子序列，又该怎么解呢？

[sdushn]

想看看大家的思路和想法，无需给出解题代码，我也继续想想

[ejq]

异或前缀和

[sdushn]

暴力解的话，应该要计算 2 的 N 次方吧，每个数都有 2 种可能性，题目给的 N 比较大，M 比较小，应该不能用暴力解

[ejq]

@sdushn 欸，这里的子数组的意思是 sub sequence 么……
高斯消元

[ejq]

二进制异或意义下的高斯消元，原数组看成一个 N*M 的矩阵

如果矩阵的秩没到 N，那么就是 YES

=》 所以如果 N > M 直接 YES ？

[sdushn]

@ejq {0, 1, 2, 3, 5}的异或前缀和是{0, 1, 3, 0, 5}，但是如果改变顺序{0, 1, 5, 2, 3}，异或前缀和就变成了{0, 1, 5, 2, 3}，这样该如何判断呢，我的理解如果是异或和为零的连续子段的话用这个方法是可行的，但是这里的字段不一定连续，似乎不太适用

[zsh1995]

今天搜狗的题？

[ejq]

计数的话，答案就是 2^(N-R) - 1 (N >= R)

R 是矩阵的秩

[sdushn]

@ejq 如果是{9,8,1}这样的可能就不符合 N>M，但是也是 YES， {0, 1, 3, 5, 9}这个例子其实 M 可以是 4，这样就是 N>M 输出 no 了。 不过我感觉确实应该用矩阵去解啊，矩阵知识忘差不多了，补一下去

[sdushn]

@ejq {0, 1, 3, 5, 9}这个的秩是不是 4 啊，好像应该把 0 元素排除掉，如果秩小于行数，那就 yes，等于就 no 了

[sdushn]

@ejq 想明白了，这个问题确实应该用矩阵来解，多谢多谢

[CDEGAE]

动态规划可解，复杂度 O(N*M)，解法可以参见这道题： http://codeforces.com/contest/1053/problem/B，不过 2 的 M 次方超过了 int 的范围，应该要当成字符串去处理。

[sdushn]

@CDEGAE 最开始我也想用动态规划的，没太想明白怎么规划，今天有些晚了，明天研究，多谢啦