This Forum is in read only mode now.

You are not logged in. Please login at www.codechef.com to post your questions!

×

NBONACCI Editorial

PROBLEM LINK:

Practice
Contest

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)$

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution

TESTER's solution

This question is marked "community wiki".

asked 25 Mar, 23:31

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 26 Mar, 00:35

nehak_21's gravatar image

0★nehak_21 ♦♦
11

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,877
×26
×4
×4

question asked: 25 Mar, 23:31

question was seen: 225 times

last updated: 26 Mar, 00:35