DP Linear Recurrence — When Matrix Exponentiation doesn't cut it

Revision en1, by cefe_origol, 2024-05-04 20:24:17

Here's a nice optimization for linear recurrence problems. This mostly works when the you're trying to find the nth term of a sequence of the form $$$f(n) = a_1 \cdot f(n-1) + a_2 \cdot f(n-2) + \dots + a_m \cdot f(n-m)$$$ where n is too large to use the normal dynamic programming approach, usually $$$ n \aprox 10^8$$$.

Tags dp, divide and conquer, matrix exponentiation, linear recurrence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English cefe_origol 2024-08-20 23:29:41 3 Tiny change: 'ot log(n))\n\nDespit' -> 'ot log(n))$\n\nDespit'. Don't know how to fix the weird latex error.
en9 English cefe_origol 2024-08-20 22:31:23 0 (published)
en8 English cefe_origol 2024-08-20 22:25:43 634
en7 English cefe_origol 2024-08-20 21:53:56 3196 Concluded, will publish soon
en6 English cefe_origol 2024-05-18 14:39:25 2450 Started added generalizations
en5 English cefe_origol 2024-05-05 00:12:45 39
en4 English cefe_origol 2024-05-05 00:05:38 2404 Added Throwing Dice
en3 English cefe_origol 2024-05-04 21:53:51 89
en2 English cefe_origol 2024-05-04 21:47:52 3483 Added solution to Magic Gems and Fibonacci Numbers
en1 English cefe_origol 2024-05-04 20:24:17 377 Initial revision (saved to drafts)