Matrix exponentiation and linear recurrence

Правка en1, от Hemanth_1, 2019-06-17 19:33:14

I was trying to solve this problem, find the n'th term of the following recurrence:

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) + n*n*(n+1)

a,b,c and the first 3 numbers in the sequence are given as the input, n can be upto 10^18 . I know that problems involving linear recurrences can be solved using matrix exponentiation, even when there are multiple sequences involved. So, in this case, if I could somehow express n*n*(n+1) as a linear recurrence as well, solving this problem becomes simple. However, I'm not able to do that, can someone help me with this ? Also, if a method to find a recurrence relation, given a closed form, exists, please mention that as well. Thanks in advance.

Теги linear recurrence, #matrix exponentialtion, #hackerearth, matrix exponentiation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Hemanth_1 2019-06-17 19:33:14 733 Initial revision (published)