 # NBONACCI Editorial

Tester & Editorialist: Hussain Kara Fallah

Easy

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)

### AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

3 Likes

Si=F1⊕F2⊕…⊕Fi should be in the editorial. Thank you for this nice editorial.

1 Like

In the author’s solution, what is the method used to take the mod in the queries loop??
why cant we just write g %= n+1 instead?

NBONACCI
Can anybody please tell what is wrong in my code? I have used similar logic and yet it is failing?

1 Like