## Problem statement

You're given infinitely many bricks of at most 15 different heights (other dimensions are not relevant here). You're also given a big integer . The task is to count the time needed to build every possible tower of height N from the given bricks. Bricks are stacked vertically only and stand in an upright position. Two towers are different if their brick height sequences are different and building one tower takes exactly 2 time units regardless of its height.

Here is the full problem statement.

## Solution

In the editorial I omit the fact that we have to count the time needed to build all towers - we will count here just the number of different towers and to get the result, you have to multiply this number by 2.

### Simpler problem first

There is a restriction, that every bricks is of height at most 15 and is at most . Lets first try to solve a simpler problem and assume that there are only bricks of height 1 or 2 and .

Let be the number of different towers of height which can be build of given bricks. In our simpler problem we have:

, because there is only one tower of height 1 consisting of one bricks of height 1

, because there are exactly two towers of height 2 - one consisting of two bricks of height 1 and the other consisting of one brick of height 2

We can now give a recursive definition for when :

because we can get one unique tower of height by placing a brick of height 1 on any tower of height and one unique tower of height also by placing a brick of height 2 on any tower of height .

If we compute bottom-up (like in dynamic programming) rather than using recursion explicitly, we can do it in time which is fine if is not as big as in the problem statement.

### Removing heights restriction

Lets remove the first restriction, so we have to deal now with bricks of at most 15 different heights (from 1 to 15).

Let indicates whether we have a brick of height :

then the general recursion equation is:

for

for

### Solving the original problem

The last thing that we have do deal with is the really big - up to . We will do it defining the recursive equation as a matrix multiplication problem and solve it using fast matrix exponentiation.

Lets assume that we've computed for using dynamic programming and let be a matrix defined as follows:

Let be the following vector:

if we multiply we get:

and we can return from here, so in order to compute for we can compute:

\begin{equation}

R = \underbrace{(M \cdot (M \cdot \dots \cdot (M}_{n - 15} \cdot V)))

\end{equation}

which can be written in the following form, because matrix multiplication is associative:

\begin{equation}

R = M^{(n-15)} \cdot V

\end{equation}

and we can compute -th power of a matrix of size it using fast exponentiation by squaring and in our problem we have and which is perfectly fine in terms of time limits. One speedup here can be to do exponentiation iteratively rather than recursively