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.
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.