一道关于异或的算法题,给你一个数列,叫你算出所有连续子序列的和的异或值就是例如（1,2,3）,连续子序列有（1）,（2）,（3）,（1,2）,（2,3）,（1,2,3）,他们的和分别是1,2,3,3,5,6,就是计算1^2^3^

Question

一道关于异或的算法题,给你一个数列,叫你算出所有连续子序列的和的异或值
就是例如（1,2,3）,连续子序列有（1）,（2）,（3）,（1,2）,（2,3）,（1,2,3）,他们的和分别是1,2,3,3,5,6,就是计算1^2^3^3^5^6的值,不能硬来的（会超时）,有什么方法呢求救

Answer 1

先求 (1) :S1 = 1,记录下S1
再求 (1,2) S2 = S1 ^ 2 ^ (2+1) = 1 ^ 2 ^ 3 = 0,记录下S2和 2,3
再求 (1,2,3) S3 = S2 ^ 3 ^ (3+2) ^ (3+3) = 0 ^ 3 ^ 5 ^ 6 = 0
设个数是N
共需要算N次,每次计算k次加法和k次异或,共计算 N(N+1)次
算法时间复杂度是 O(N平方),空间复杂度是O(N)
这个复杂度是不会超时的.
如果直接硬来,
长度为k的子序列数量有 N+1-k 个
则共有N(N+1)/2个子序列,每个自序列需要计算k次加法.
最后大约计算 K的三次方/3 次加法,最后
这个时间复杂度是 O(N的3次方),空间复杂度是O(1)
通过记录中间值,以空间换时间,应该可以.