All Tracks Algorithms Dynamic Programming Problem

Fibonacci substrings 2

Algorithms, Combinatorics, Dynamic Programming, Fibonacci numbers, Medium-Hard


Anna as well as Masha likes Fibonacci numbers and she also represents all natural numbers as sum of Fibonacci numbers. Girls call it Fibonacci number system.

Fibonacci numbers is a sequence f, which is defined as follows: \(f_0 = f_1 = 1\) and \(f_i = f_{i-1}+f_{i-2}\) for all \(i>1\).

Numbers in Fibonacci number system are represented as binary strings with no leading zeros and no two ones are consecutive. To represent natural number n in this system, one has to represent n as the sum of non-consecutive Fibonacci numbers: \(n=f_{i_1}+f_{i_2}+\dots+f_{i_m}\) such that \(i_j>0\) and \(|i_j-i_k|>1\) for all \(1 \le i, j \le m\), \(i \ne j\). For example, let's say \(n=7\), we can represent \(n = 7 = 2 + 5 = f_2 + f_4\), so 7 in Fibonacci number system is 1010, \(n=12\) represented as 10101 and \(n=1\) — as 1.

Masha got a piece of paper and started writing a big binary string \(s=s_1s_2s_3 \ldots\). Binary string s is formed as follows: initially she has empty string, then she appends Fibonacci number system representation of every natural number starting with 1 in increasing order. So the beginning of her string looks as follows: 110100101100010011010.... These are numbers from 1 to 7, their Fibonacci number system representations are: 1, 10, 100, 101, 1000, 1001, 1010.

Masha is very patient and hard-working, so she wrote a string s of length \(10^{18}\). Anna found a piece of paper with a part of string s, written by Masha, along with integers L and R. She guessed that this piece of paper contains \(s_Ls_{L+1} \ldots s_R\). Anna likes substrings, so she wants to know number of occurrences of substrings 00, 01, 10 and 11 on this piece of paper.

Input format

Input consists of single line containing two integers L and R.


\(1 \le L \le R \le 10^{18}\)

Output format

Output four integers \(c_{00}\), \(c_{01}\), \(c_{10}\) and \(c_{11}\) — number of occurrences of substrings 00, 01, 10 and 11 in string \(s_Ls_{L+1} \ldots s_R\), respectively.

11 19
3 2 2 1

A piece of paper for sample test contains string 000100110.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

February Easy '17

View All Notifications