PROBLEM LINK:Author: Erfan alimohammadi DIFFICULTY:Easy PREREQUISITES:None PROBLEM:An Nbonacci 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 Nbonacci 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:
This question is marked "community wiki".
asked 25 Mar, 23:31
