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)
And the question arise when I encounter this problem 506E — Mr. Kitayuta's Gift, I write a dp solution below.
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.