kkts's blog

By kkts, history, 7 weeks ago, In English

Can anyone solve this?

We have to answer Q queries, each of them contains three integers k , l , r.

Query asks us to calculate the XOR of the Fibonacci numbers with indexes in the interval [l,r] inclusive, indexed from 0, modulo 2^k.

Constraints:

•1≤Q≤10^6

•0≤l≤r≤10^18

•1≤k≤20

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

The period of the Fibonacci sequence modulo $$$n=2^k$$$ is $$$3n/2$$$, according to Wikipedia. This means that prefix-xor will have a period of $$$3n$$$. So, the solution would be to just compute the first $$$3n$$$ values of the prefix-xor of the fibonacci sequence modulo $$$2^k$$$, and the answer to a query is simply $$$p[(r+1) \mod 3n] \text{ xor } p[l \mod 3n]$$$ , where, of course, $$$p[i]$$$ is the xor of $$$f_0, f_1, \ldots, f_{i-1}$$$ and $$$p[0] = 0$$$.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

$$$Fib_n\%2^k$$$ is periodic with period $$$3 \cdot 2^{k - 1}$$$.

Precompute for each $$$k$$$ an array, which stores the Fibonacci elements till a full period. Since period is equal to $$$3n/2$$$, this precompuation won't TLE, even for $$$k = 20$$$.

Once you have that, just manipulate prefix xor.