kkts's blog

By kkts, history, 7 weeks ago,

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

• +12

 » 7 weeks ago, # |   +16 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, # |   +6 $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.