PROBLEM LINK:
Author: Erfan alimohammadi
Tester & Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
An N-bonacci sequence is an infinite sequence F_1,F_2,… such that for each integer i>N:
F_i =F_{i−1}⊕F_{i−2}⊕…⊕F_{i−N} where ⊕ denotes the bitwise XOR operation.
Recently, Chef has found an interesting sequence S_1,S_2,… , which is obtained from prefix XORs of a XOR N-bonacci sequence F_1,F_2,….
Formally, for each positive integer i :
S_i=F_1⊕F_2⊕…⊕F_i.
You are given the first N elements of the sequence F, which uniquely determine the entire sequence S.
You should answer Q queries. In each query, you are given an index k and you should calculate S_k. It is guaranteed that in each query.
1\leq N,Q \leq 10^5
1\leq K \leq 10^9
EXPLANATION:
Let’s mention some important observations:
F_{N+1} \,=\, F_1⊕F_2⊕…⊕F_N
Let’s take one step forward and calculate F_{N+2}. You will notice that:
F_{N+2} \, = \, F_2⊕F_3⊕F_4⊕…⊕F_N⊕F_{N+1}
We already defined F_{N+1} and we know that X⊕X=0
So we conclude F_{N+2} = F_1
Based on the same terminology, we can see that our sequence F look like this:
\{F_1,F_2,F_3,...,F_N, \,TotalXor \, ,F_1,F_2,F_3,...,F_N,\, TotalXor \,,....\}
Now as defined in the problem statement:
S_i = F_1⊕F_2⊕…⊕F_N
Let’s calculate the value of S_i for each i such that (1 \leq i \leq N+1) We can do that in linear time.
You should notice that S_{N+1}=0 because all elements are included twice in its total expression.
So At last:
S_K = S_{K\,mod\,N+1}
Assuming that S_0=0 since it represents empty sequence.
Complexity: O(N)