c++ - 计算相邻异或

Question

输入是一个最多包含 1000,000 个元素的布尔数组a_0,i。

每次新数组由xor前一个数组中的相邻（循环）元素组成时：

a_t,i = a_t-1,i ^ a_t-1,(i+1)%n     // n is size of input

需要第 p 个数组 (a_p,i)。(p <= 1000,000,000)。

根据上限，p我认为可能存在数组结构，或者数组可以在O(lg(p) * n).

Answer 1

如果 t 是 2 的幂 (t=2 ^k )，

a_t,i = a_0,i ^ a_0,(i+t)%n

此外，如果 t 是两个分量的和，其中一个是 2 的幂 (t = v + w, w=2 ^m )，

a_t,i = a_v,i ^ a_v,(i+w)%n

这允许使用 p 的二进制表示来递归地计算结果数组。复杂度按要求：O(lg(p) * n)：

shift = 1;
while (p != 0)
{
  if (p&1)
    a ^= a.rotate(shift);
  shift *= 2
  p /= 2
}