Connection Status:
Competition Arena > FibonacciXor

FibonacciXor

SRM 622 · 2013-12-22 · by ltaravilse

SRM 622 · 2013-12-22 · by ltaravilse · Advanced Math, Dynamic Programming
Class Name: FibonacciXor
Return Type: int
Method Name: find
Arg Types: (long long, long long)
Problem Statement

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 > 0:
        find the largest Fibonacci number f <= 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:
  1. Use the above algorithm to find a representation of n in Fibonacci base.
  2. Take the sequence of digits obtained in step 1, and interpret it as a binary number (i.e., a number in base 2).
  3. 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.

Constraints

  • B will be between 1 and 10^15, inclusive.
  • A will be between 1 and B, inclusive.
Examples
0)
1
2
Returns: 3

We have g(1)=1, g(2)=2, and (1 xor 2)=3.

1)
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.

2)
1
1000000000000000
Returns: 780431495

Don't forget the modulo 1,000,000,007.

3)
2
100
Returns: 157
4)
1
1
Returns: 1

Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FibonacciXor with a public method int find(long long A, long long B) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous