### coderdhanraj's blog

By coderdhanraj, 6 weeks ago, Hey Everyone!, I was trying this problem with Matrix Exponential as I got a recurrence relation of ${f_k = f_{k-9} + f_{k-10}}$.

I am unable to speed up the matrix exponentiation as it's gonna be ${O(10^3 * log k)}$ to get Matrix $M_{10 * 10}^k$ to get $f_k$.

Can anyone tell me some optimizations to get $f_k$ faster? Comments (4)
 » 6 weeks ago, # | ← Rev. 3 →   A hint$m$ is small, so precompute and use $O(m*10^3)$ exponentation.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   If I would precompute wouldn't it become a simple dp problem?Actually I saw the same problem on some other platform where the constraints were ${m \le 10^9}$.That's why I am looking for a ${log(m)}$ solution.As we calculate nth term fibonacci ${f_n = f_{n-1} + f_{n-2}}$ in $O{(2^3 * log(n))}$ as we required only 2 previous states so we used to have a ${2 * 2}$ matrix so can we do something here? we are looking only for 2 previous states, i.e. ${f_{n-9}}$ and ${f_{n-10}}$, can we optimise the matrix ${10 * 10}$ to ${2 * 2}$?
 » 6 weeks ago, # | ← Rev. 3 →   You can read the editorial of this DMOJ problem. Apparently you can remove a factor $10$ if you have multiple queries.
•  » » Thanks, it's very useful! :P