Editorial for DMOPC '20 Contest 1 P4 - Victor Makes Bank
Submitting an official solution before solving the problem yourself is a bannable offence.
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:
For 20% of points, we can implement this transition directly with two nested for loops.
For the remaining 80% of points, we note the transformation is linear, and 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.