Fibonacci Calculation


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

The Fibonacci sequence is defined by the following relation:

F(0) = 0,
F(1) = 1,
F(N) = F(N - 1) + F(N - 2), N \ge 2

Your task is very simple. Given two non-negative integers N and M: you have to calculate the sum [F(N) + F(N + 1) + ... + F(M)] \mod 1000000007.

Input specification

The first line contains an integer T \leq 1000 (the number of test cases). Then, T lines follow. Each test case consists of a single line with two non-negative integers N and M, 0 \leq N \leq M \leq 10^9.

Output specification

For each test case you have to output a single line containing the answer for the task.

Sample input

3
0 3
3 5
10 19

Sample output

4
10
10857

Comments


  • 1
    CarlosJavier  commented on Jan. 20, 2023, 5:24 p.m.

    Hola, el problema me da TLE, estoy usando exponenciacion de matrices para encontrar Fn y Fn+1 de la secuencia de fibonacci, entonces solo voy sumando. Aun asi se me va en tiempo, alguien que pueda ver mi codigo y decirme en que puedo mejorarlo. Gracias de antemano.


    • 2
      linkyless  commented on Jan. 21, 2023, 8:14 p.m.

      La idea está en simplemente calcular solo los Fibo numbers que necesitas para resolver el ejercicio, en vez de calcular y pasar por todos. La fórmula F(m + 1) - F(n) donde F(n) es el número n de Fibonacci y F(m) es el número m de Fibonacci te da para calcular en una sola operación la suma de todos los números de Fibonacci de n a m.

      PD: También funciona para F(m + 2) + F(n - 1) y todos los subsecuentes.

      Con Exponenciación de Matrices te da para dividir y calcular la suma con la fórmula.


      • 1
        aniervs  commented on Jan. 21, 2023, 11:59 p.m.

        Añadí en la editorial una solución que no necesita potenciación de matrices.


  • 0
    legion06  commented on Dec. 30, 2022, 4:41 p.m.

    alguien me puede decir porq me da rte


    • 0
      josue  commented on Jan. 1, 2023, 7:17 p.m.

      No puedes almacenar 10^9 enteros en un vector


  • -3
    angelmh  commented on April 18, 2021, 7:05 p.m.

    Ya este ejercicio lo he aceptado en otros jurados online, no se por qué aca no da nada bien. La solución que uso es exponenciación de matrices


  • -2
    FabioVergelP  commented on Jan. 6, 2021, 3:53 p.m.

    que significa RTE? :v


  • -9
    PedroPabloAB  commented on Jan. 4, 2021, 6:08 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    PedroPabloAB  commented on Jan. 3, 2021, 4:19 a.m.

    Por qué da RTE?


    • 5
      josed  commented on Jan. 3, 2021, 10:54 p.m.

      N y M pueden ser hasta 10^9 sin embargo estás usando un arreglo de tamaño 2000000 para guardar las soluciones ?


  • -1
    Osnielfc_07  commented on June 8, 2020, 1:54 p.m.

    ¿ Por que me dan los tres primeros casos MLE ?.