coderdhanraj's blog

How to solve it with Matrix Exponential?
By coderdhanraj, 20 months ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
20 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
A hint
→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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}$$$?

    → Reply
»
20 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

You can read the editorial of this DMOJ problem. Apparently you can remove a factor $$$10$$$ if you have multiple queries.

→ Reply