Блог пользователя coderdhanraj

How to solve it with Matrix Exponential?
Автор coderdhanraj, 20 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
20 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
A hint
→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
    ← 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}$$$?

    → Ответить
»
20 месяцев назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить