Fibonacci Calculation

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

leo

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(0) = 0~,
$F(1) = 1$ ~F(1) = 1~,
$F(N) = F(N - 1) + F(N - 2)$ ~F(N) = F(N - 1) + F(N - 2)~, $N \ge 2$ ~N \ge 2~

Your task is very simple. Given two non-negative integers $N$ ~N~ and $M$ ~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$ ~T \leq 1000~ (the number of test cases). Then, $T$ ~T~ lines follow. Each test case consists of a single line with two non-negative integers $N$ ~N~ and $M$ ~M~, $0 \leq N \leq M \leq 10^9$ ~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

Sample output

4
10
10857

Comments

2

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.

2

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

1

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

-10

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

Qué va! No logro hacer este ejercicio. Para valores pequeños me da bien, pero no para los valores muy grandes.

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

-4

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$ ~N~ y $M$ ~M~ pueden ser hasta $10^9$ ~10^9~ sin embargo estás usando un arreglo de tamaño $2000000$ ~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 ?.