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?
$$$m$$$ is small, so precompute and use $$$O(m*10^3)$$$ exponentation.
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}$$$?
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