Fibonacci series


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

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

Definamos la secuencia de los números de Fibonacci como:

F_1 = 1

F_2 = 2

F_n = F_{n - 1} + F_{n - 2} para n \ge 3

Los primeros elementos de la secuencia son 1, 2, 3, 5, 8, 13, 21,. . .

Para un entero positivo p, sea X(p) el número de formas diferentes de expresar p como una suma de diferentes Números de Fibonacci. Dos formas se consideran diferentes si hay un número de Fibonacci que existe exactamente en una de ellos.

Se le da una secuencia de n enteros positivos a_1, a_2,... , a_n. Para un prefijo no vacío a_1, a_2,... , a_k, nosotros definimos a p_k = F_{a_1} + F_{a_2} +... + F_{a_k}.

Tarea

Su tarea es encontrar los valores X(_{p_k}) módulo 10^9 + 7, para todo k = 1,... , n.

Entrada

La primera línea de la entrada estándar contiene un entero n (1 \le n \le 100 000). La segunda linea contiene n enteros separados por espacios a_1, a_2,... , a_n (1 \le a_i \le 10^9).

Salida

La salida estándar debe contener n líneas. En la k-th línea, imprima el valor X(_{p_k}) módulo (10^9 + 7).

Ejemplo de Entrada

4
4 1 1 5

Ejemplo de Salida

2
2
1
2

Explicación del ejemplo:

Tenemos los siguientes valores p_k:

p_1 = F_4 = 5

p_2 = F_4 + F_1 = 5 + 1 = 6

p_3 = F_4 + F_1 + F_1 = 5 + 1 + 1 = 7

p_4 = F_4 + F_1 + F_1 + F_5 = 5 + 1 + 1 + 8 = 15

El número 5 se puede expresar de dos maneras: como F_2 + F_3 y simplemente como F_4 (es decir, 2 + 3 y 5, respectivamente).

Por lo tanto, X(_{p_1}) = 2.

Entonces tenemos X(p_2) = 2 porque p_2 = 1 + 5 = 1 + 2 + 3.

La única manera de expresar 7 como una suma de diferentes números de Fibonacci es 2 + 5.

Finalmente, 15 se puede expresar como 2 + 13 y 2 + 5 + 8 (dos formas).

Calificación

El conjunto de prueba se divide en las siguientes subtareas con restricciones dicionales. Cada una de las subtareas consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea Restricciones y Puntos

1   n, a_i \le 15   5 Puntos

2   n, a_i \le 100   20 Puntos

3   n ≤ 100, a_i   son cuadrados de diferentes números naturales    15 Puntos

4   n ≤ 100   10 Puntos

5   a_i   son números pares diferentes    15 Puntos

6   sin restricciones adicionales    35 Puntos


Comments

There are no comments at the moment.