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

sdushn · 2018-09-27T14:30:58Z

给定一个 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}这样的数据就不知道该怎么样做比较好了。拓展：如果问题升级，输出存在几个这样的子序列，又该怎么解呢？

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 2787 days ago, the information mentioned may be changed or developed.

给定一个 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}这样的数据就不知道该怎么样做比较好了。
拓展：如果问题升级，输出存在几个这样的子序列，又该怎么解呢？