Xor-sequence

  • + 0 comments

    Even we know how to calculate the Ai value with the pattern of %4, it is still no enough to solved this problem within time limit. However, there is also a pattern for Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k. The idea is that Ai,Ai+1,Ai+2,Ai+3 can be considered as a set, where i%4 == 0. Thus, Ai⊕Ai+1⊕Ai+2⊕Ai+3 = i⊕1⊕i+2⊕0 = 2. Therefore, Ai⊕Ai+1⊕Ai+2⊕....⊕Ai+k = Al-2⊕Al-1⊕Al⊕2⊕2⊕...⊕2⊕Ar⊕Ar+1, where l is the smallest number and r is the larget number can be divided by 4 within the range of [L,R]. As a result, the key is to find the XOR at the front and end sequnce and count how many 2's in between.