## Editorial for DMOPC '20 Contest 1 P4 - Victor Makes Bank

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Let be the number of baby crabs that are months old, and let be the number of crabs that are adults. The transition from month to month is given by

##### Subtask 1

For 20% of points, we can implement this transition directly with two nested for loops.

**Time Complexity:**

##### Subtask 2

For the remaining 80% of points, we note the transformation is linear, we can represent it with the matrix :

where is the identity matrix.

Then we can obtain the answer with

We can compute quickly using binary exponentiation.

**Time Complexity:**

## Comments

I think I found an error: the matrix should actually be size by to represent each of the T months that a crab is a baby PLUS the one final state in which it is an adult. This was how I implemented my solution.

Thank you, it has been fixed.