Fibonacci 2D

Points: 100 (partial)

Time limit: 2.0s

Java 8 4.0s

Python 5.0s

Memory limit: 64M

Authors:

ralcolea, raikiri, jabetancourt

Problem type

Allowed languages

Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

La secuencia de Fibonacci es una de las secuencias más conocidas en las ciencias de la computación. Esta secuencia define que el término $f(n) = f(n-1) + f(n-2)$ ~f(n) = f(n-1) + f(n-2)~ y los casos bases son $f(0) = 0$ ~f(0) = 0~ y $f(1) = 1$ ~f(1) = 1~.

En este problema, se ha definido otra secuencia de Fibonacci inspirada en la secuencia original, pero en dos dimensiones. La nueva secuencia recibe el nombre de Fibonacci 2D y define que el término $f(x, y) = f(x-1, y) + f(x, y-1) + f(x-1, y-1)$ . Los casos base son $f(x, 0) = f(0, y) = 1$ ~f(x, 0) = f(0, y) = 1~. Escriba un programa que calcule el valor de la secuencia de Fibonacci 2D dados los valores $x$ ~x~ e $y$ ~y~.

Entrada

La primera línea contiene un número entero, $1 \le T \le 100$ ~1 \le T \le 100~, el número de casos de prueba. Las siguientes $T$ ~T~ líneas contienen los enteros $x$ ~x~ e $y$ ~y~ para los cuales se desea calcular la respuesta del problema. En la entrada siempre se garantiza que los valores $x$ ~x~ e $y$ ~y~ estarán en el rango $[0..1000]$ ~[0..1000]~.

Salida

Para cada caso de prueba, imprima el valor de la secuencia $f(x, y)$ ~f(x, y)~ para los valores de $x$ ~x~ e $y$ ~y~ dados en la entrada. Debido a que el valor de la función puede crecer muy rápido, imprima el valor de la respuesta módulo $1000000007$ ~1000000007~.

Ejemplo de entrada

Ejemplo de salida

63
1
206914827

Comments

0

Jaimemm commented on Dec. 10, 2024, 5:47 a.m.

Me da RTE en los casos 6 y 8, todo lo demas AC, por que puede ser esto?

0

marco_b_32 commented on Feb. 2, 2024, 3:31 p.m.

como hacer la ecuacion en c++

2

karellgz commented on Feb. 2, 2024, 6:11 p.m.

Vi que estás usando una solución recursiva, si no utilizas memoización no te va a funcionar para $x,y>12$ ~x,y>12~

Leete esto

También mira bien en dónde aplicas (o deberias aplicar) módulo

2

Learning_C commented on Dec. 15, 2023, 9:14 p.m.

[Error] invalid operands of types 'long long int' and 'double' to binary 'operator%'

que significa esto? Me da error a la hora de responder con modulo?

2
karellgz commented on Dec. 15, 2023, 9:32 p.m.
Cuando calculas $n \mod m$ ~n \mod m~, $n$ ~n~ y $m$ ~m~ deben ser necesariamente enteros.

double MOD = 1000000007; //Cambialo a: long long MOD = 1000000007; //o tambien si usas la macro: #define MOD 1e9+7 //Cambialo entonces a: #define MOD 1000000007 ... fibo[n] % MOD

0

Soyyo commented on Feb. 21, 2023, 6:38 p.m.

Alguien me podria explicar como hacer eso que dice de la "respuesta modulo"

4

Kojima_Cubano_veriffedXD commented on March 1, 2023, 12:19 p.m.

CADA RESULTADO has de darlo utilizando ese modulo osea x%1000000007