Digamos que ~f_n~ es la cantidad de secuencias que suman ~n~. Cualquier secuencia válida, debe empezar por 1 o 2.

• En el caso de que empiece por ~1~, los restantes números deben sumar ~n - 1~.
• En el caso de que empiece por ~2~, los restantes números deben sumar ~n - 2~.

Entonces, podemos formular la siguiente recurrencia:

$$\displaystyle \begin{align} f_0 = 1\\ f_1 = 1\\ f_n = f_{n-1} + f_{n-2} & \forall n > 1 \end{align} $$

Para el 40 % de los casos de prueba, es suficiente implementar una solución en complejidad ~\mathcal{O}(n)~, pero para obtener todos los puntos se necesita algo sublineal. En particular, buscaremos una solución con complejidad temporal ~\mathcal{O}(\log n)~.

Potenciación de matrices

Se puede usar de manera estándar la técnica de potenciación de matrices. Visitar este link para aprender sobre potenciación de matrices

Otra solución

Observemos la recurrencia. Digamos que los valores iniciales son ~a, b~ respectivamente. Entonces, la secuencia luce así:

~a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, 5a + 8b, \dots~

Notemos que los coeficientes de ~a~ y ~b~ en cada término de la recurrencia son los números de fibonacci. Podemos hipotizar que el ~n~-ésimo de una recurrencia con la ecuación dada, y con ~f_0 = a~ y ~f_1 = b~ es ~a \cdot Fib_{n-1} + b \cdot Fib_{n}~. Más formalmente dicho, ~f_{n + k} = f_n \cdot Fib_{k-1} + f_{n+1} \cdot Fib_{k}~. Esto se puede demostrar fácilmente por inducción, o también a partir de potenciación de matrices.

Es obvio que en nuestro caso, la recurrencia es simplemente la secuencia de fibonacci omitiendo el 0.

Basados en dicha entidad, podemos concluir que:

~ f_{2n} = f_n \cdot (2 f_{n+1} - f_n) ~

~ f_{2n} = f_n \cdot (f_n + 2 f_{n-1}) ~

~ f_{2n + 1} = f_n^2 + f_{n+1}^2 ~

~ f_{2n + 1} = f_n^2 + (f_n + f_{n-1})^2 ~

Podemos usarlas parar computar ~f_n~ en tiempo ~\mathcal{O}(\log n)~. Podemos tener una función solve(n) que retorne el valor de ~f_{2n}~ y ~f_{2n + 1}~, usando las fórmulas mostradas previamente.