c++ - 隣接するXORを計算する

Question

入力は、a_0,i最大1000,000要素のブール配列です。

新しい配列が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つの成分の合計であり、そのうちの1つが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
}