Problem link : contest
practice
Difficulty : Hard
Pre-requisites : Matrix exponentiation, dp
Solution :
- When X = 1, You can do a simple dp. For optimizing that dp, you need to use matrix exponentiation.
- When X = 2, Idea is similar, but this time rows and coloumns of matrix will be larger.
- When X = 3, You can notice that matrix created will be sparse, You can use this observation very well. As N is very small. Assume you want to compute A^n where n is small. Note that we will
keep multiplying A by A, then A^2 by A, then A^3 by A, In the process we are always doing a multiplication by a sparse matrix.
You can also do a dp here too. You don’t need matrix exponentiation too.
Setter’s solution: link