FibonacciXor | Topcoder Archive

Problem Statement

The Fibonacci sequence is defined as follows:

F[0] = 0
F[1] = 1
for each i >= 2: F[i] = F[i-1] + F[i-2]

Thus, the Fibonacci sequence starts as follows: 0, 1, 1, 2, 3, 5, 8, 13, ... The elements of the Fibonacci sequence are called Fibonacci numbers.

Fibonacci base is a positional numeral system. The only two allowed digits are 0 and 1. The weights assigned to positions in the number are all distinct positive Fibonacci numbers, in order. For example, in Fibonacci base the sequence of digits 1101 represents the number 1*5 + 1*3 + 0*2 + 1*1 = 9. Some numbers have more than one representation in Fibonacci base. For example, we can also represent 9 as 10001, because 1*8 + 0*5 + 0*3 + 0*2 + 1*1 = 9.

Consider the following greedy algorithm:

decompose(n):
    L = an empty list
    while n &gt; 0:
        find the largest Fibonacci number f &lt;= n
        append f to L
        n = n-f
    return L

It can easily be shown that the above algorithm will write any positive integer n as a sum of distinct Fibonacci numbers. In other words, the above algorithm chooses one particular representation of n in Fibonacci base. For example, for n=9 we get the representation 10001 (i.e., 8+1), and for n=30 we get 1010001 (i.e., 21+8+1).

We can now define a new function g. The value g(n) is computed as follows:

Use the above algorithm to find a representation of n in Fibonacci base.
Take the sequence of digits obtained in step 1, and interpret it as a binary number (i.e., a number in base 2).
Return the value of that binary number.

For example, suppose that n=30. First, we compute that 30 in Fibonacci base is 1010001. Next, we compute that 1010001 in base 2 is 64+16+1=81. Hence, g(30)=81.

You are given longs A and B. Compute and return the following value: (g(A) xor g(A+1) xor g(A+2) xor ... xor g(B-2) xor g(B-1) xor g(B)) modulo 1,000,000,007.

Definition

Class:: FibonacciXor
Method:: find
Parameters:: long, long
Returns:: int
Method signature:: int find(long A, long B)
(be sure your method is public)

Constraints

B will be between 1 and 10^15, inclusive.
A will be between 1 and B, inclusive.

Examples

```
1
```
```
2
```
```
Returns: 3
```
We have g(1)=1, g(2)=2, and (1 xor 2)=3.
```
3
```
```
10
```
```
Returns: 25
```
Our greedy algorithm chooses the following Fibonacci base representations for the numbers 3 through 10: 00100 00101 01000 01001 01010 10000 10001 10010 (Note that for clarity we included some leading zeros in some of the representations.) If we consider these as base-2 numbers, their values are 4, 5, 8, 9, 10, 16, 17, and 18. Thus, the answer is (4 xor 5 xor 8 xor ... xor 18) = 25.
```
1
```
```
1000000000000000
```
```
Returns: 780431495
```
Don't forget the modulo 1,000,000,007.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.