Question about Cayley-Hamilton theorem and estimating the number of terms of linear recurrence

Revision en2, by Misuki, 2022-04-11 15:40:55

Recenetly I was learning Berlekamp-Massey and applying it when our dp can be seen as a linear recurrence, if you don't know how it works, here is an simple description of it.(or a more detail description in this blog)

simple description

And the question arise when I encounter this problem 506E — Mr. Kitayuta's Gift, I write a dp solution below.

Spoiler

Apparently, we can see $$$dp[i]$$$ as a $$$|s|^2$$$ times $$$1$$$ vector, which means the size of transition matrix will be $$$|s|^2$$$ times $$$|s|^2$$$, so according to Cayley-Hamilton theorem, the linear recurrence of this dp will have at most $$$|s|^2$$$ terms, so if we compute the first $$$2|s|^2$$$ vectors of $$$dp[i] (i \le 2|s|^2)$$$ then plug them into Berlekamp-Massey, calculate $$$dp[(n + |s|) / 2]$$$, the time complexity will be $$$O(26|s|^4 + |s|(|s|^2 + |s|^2lg(n+|s|))$$$, which obviously will not fit in the TL.

But it turns out that it will only have about $$$350$$$ terms at most, which is far from $$$|s|^2$$$, and will fit in the TL, you can see my submission. Here comes the question, do we have any method to estimate how many terms a linear recurrence have? If we don't, then how to determine the number of terms we need to compute to plug into Berlekamp-Massey?

btw, sorry for my bad english.

Tags berlekamp-massey, cayley-hamilton, linear recurrence, question

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Misuki 2022-04-11 15:42:02 15 (published)
en2 English Misuki 2022-04-11 15:40:55 2314 Tiny change: 've atmost n terms, s' -> 've atmost $n terms, s'
en1 English Misuki 2022-04-11 14:08:35 1614 Initial revision (saved to drafts)