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?

• +6

 » 6 weeks ago, # | ← Rev. 3 →   0 A hint$m$ is small, so precompute and use $O(m*10^3)$ exponentation.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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 →   +1 You can read the editorial of this DMOJ problem. Apparently you can remove a factor $10$ if you have multiple queries.
•  » » 6 weeks ago, # ^ |   0 Thanks, it's very useful! :P