FIBEQN - Editorial

advanced-math
editorial
fibonacci
ipc15p3b
matrix-expo

#1

FIBEQN Editorial by Satwant Rana

The problem asks us to calculate \sum_{i = 0}^n{F_i\ k^i}, and time limit suggests we need to do it in O(log\ N) time.

The model solution makes use of the fact that F_i = \frac{\phi^i - \psi^i}{\phi-\psi}, where \phi = \frac{1 + \sqrt5}{2} and \psi = \frac{1 - \sqrt5}{2}. Leveraging this fact we can perform computations in \mathbb Z[\sqrt5].

So the problem asks us to calculate \sum_{i = 0}^n{\frac{\phi^i - \psi^i}{\phi-\psi}\ k^i} = \frac{\frac{(\phi\ k)^i - 1}{\phi - 1} - \frac{(\psi\ k)^i - 1}{\psi - 1}}{\phi - \psi}. This can be done in O(log N) time with logarithmic exponentiation in \mathbb Z[\sqrt5].

Setter’s Solution