这是一个创建于 2248 天前的主题，其中的信息可能已经有所发展或是发生改变。
- 给定一个 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}这样的数据就不知道该怎么样做比较好了。
- 拓展：如果问题升级，输出存在几个这样的子序列，又该怎么解呢？
 |
1
sdushn OP 想看看大家的思路和想法，无需给出解题代码，我也继续想想
|
 |
2
ejq 2018-09-27 22:35:03 +08:00  1
异或前缀和
|
|
3
sdushn OP 暴力解的话，应该要计算 2 的 N 次方吧，每个数都有 2 种可能性，题目给的 N 比较大，M 比较小，应该不能用暴力解
|
|
5
ejq 2018-09-27 22:58:08 +08:00
二进制异或意义下的高斯消元，原数组看成一个 N*M 的矩阵
如果矩阵的秩没到 N，那么就是 YES =》 所以如果 N > M 直接 YES ？ |
|
6
sdushn OP @ejq {0, 1, 2, 3, 5}的异或前缀和是{0, 1, 3, 0, 5}，但是如果改变顺序{0, 1, 5, 2, 3}，异或前缀和就变成了{0, 1, 5, 2, 3}，这样该如何判断呢，我的理解如果是异或和为零的连续子段的话用这个方法是可行的，但是这里的字段不一定连续，似乎不太适用
|
 |
7
zsh1995 2018-09-27 22:59:55 +08:00
今天搜狗的题？
|
|
8
ejq 2018-09-27 23:00:12 +08:00
计数的话，答案就是 2^(N-R) - 1 (N >= R)
R 是矩阵的秩 |
|
9
sdushn OP @ejq 如果是{9,8,1}这样的可能就不符合 N>M，但是也是 YES， {0, 1, 3, 5, 9}这个例子其实 M 可以是 4，这样就是 N>M 输出 no 了。 不过我感觉确实应该用矩阵去解啊，矩阵知识忘差不多了，补一下去
|
|
10
sdushn OP @ejq {0, 1, 3, 5, 9}这个的秩是不是 4 啊，好像应该把 0 元素排除掉，如果秩小于行数，那就 yes，等于就 no 了
|
 |
12
CDEGAE 2018-09-27 23:52:58 +08:00 1
动态规划可解，复杂度 O(N*M)，解法可以参见这道题： http://codeforces.com/contest/1053/problem/B，不过 2 的 M 次方超过了 int 的范围，应该要当成字符串去处理。
|
Select Language