Fibonacci series
Definamos la secuencia de los números de Fibonacci como:
para
Los primeros elementos de la secuencia son 1, 2, 3, 5, 8, 13, 21,. . .
Para un entero positivo , sea el número de formas diferentes de expresar 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 enteros positivos . Para un prefijo no vacío , nosotros definimos a .
Tarea
Su tarea es encontrar los valores módulo , para todo .
Entrada
La primera línea de la entrada estándar contiene un entero . La segunda linea contiene enteros separados por espacios .
Salida
La salida estándar debe contener líneas. En la línea, imprima el valor módulo .
Ejemplo de Entrada
4
4 1 1 5
Ejemplo de Salida
2
2
1
2
Explicación del ejemplo:
Tenemos los siguientes valores :
El número se puede expresar de dos maneras: como + y simplemente como (es decir, y , respectivamente).
Por lo tanto, .
Entonces tenemos porque .
La única manera de expresar 7 como una suma de diferentes números de Fibonacci es .
Finalmente, 15 se puede expresar como y (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
n 5 Puntos
n 20 Puntos
n ≤ 100 son cuadrados de diferentes números naturales 15 Puntos
n ≤ 100 10 Puntos
a_i son números pares diferentes 15 Puntos
sin restricciones adicionales 35 Puntos
Comments