Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Matrix exponentiation and linear recurrence

Revision en1, by 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.

Tags linear recurrence, #matrix exponentialtion, #hackerearth, matrix exponentiation


  Rev. Lang. By When Δ Comment
en1 English Hemanth_1 2019-06-17 19:33:14 733 Initial revision (published)