인접한 xor를 계산합니다.

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 ^K)의 전원 인 경우, 또한

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

, t는 두 성분의 합이며, 그 중 하나가 2의 제곱 (경우 t = V +, w 2 ^미터) = w

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 
}