Rating:

# Crunchy

We are given a small Python program which computes the flag:


def crunchy(n):
if n < 2: return n
return 6 * crunchy(n - 1) + crunchy(n - 2)

g = ... # a _really_ big number


Running this, of course, won't get us anywhere with the exponentially
slow implementation of crunchy. A simple improvement would be to
cache computed vaues of crunchy(n), but that reduces the complexity
to linear, which is still not nearly enough with the hundred-digit
parameter.

Since crunchy is a linear recurrence, we can compute it in
logarithmic time. We can express the mapping from $(c(n), c(n-1))$ to
$(c(n+1), c(n))$ (where $c$ is the function) as a matrix multiplication:

$$\begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} = \begin{pmatrix}6&1\\1&0\end{pmatrix} \begin{pmatrix}c(n)\\c(n-1)\end{pmatrix}$$

If we expand the right-hand side of this equation $n-1$ times, we will
get:

$$\begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} = \begin{pmatrix}6&1\\1&0\end{pmatrix}^n \begin{pmatrix}c(1)\\c(0)\end{pmatrix}$$

Since we know the values of $c(1)$ and $c(0)$, all that remains is to
compute the exponentiated matrix. We can do this in
$\mathcal{O}(\log{n})$ multiplications by [repeated
squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring),
which is completely reasonable for the input value of g (a few
hundreds of multiplications).

Note that all multiplications should be done modulo $10^9 + 7$ instead
of only doing so at the end -- otherwise, the intermediate values will
be to large to work with (they grow exponentially).