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.
Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).
Cayley-Hamilton theorem states that the characteristic polynomial $$$P$$$ of matrix $$$A$$$ satisfies $$$P(A) = 0$$$, which, indeed, bounds the order of recurrence from above. However, in general characteristic polynomial may be not the one with the smallest degree satisfying this property. See https://en.m.wikipedia.org/wiki/Minimal_polynomial_(linear_algebra)
Thanks for your reply!
In that article, it did not mention estimation about the degree of minimal polynomial, so in practical, I guess all we can do is just generate as many terms as possible in TL and praying it will pass if generate n terms will be too slow?
Estimating the degree of the minimal polynomial varies based on the problem and is usually done by examining the naive DP solution. It's also not always straightforward. For example, in this problem the bound the editorial provides for the size of the transition matrix is $$$161 \times 161$$$ by analyzing redundant states.
Personally, I find one of the biggest advantages of Berlekamp-Massey is that it lets you be more brain dead. Berlekamp-Massey is rarely required in a problem because you could always figure out the transition yourself, but it makes life so much easier precisely because you can just calculate as many terms as possible in TL and pray it works.
As far as I can see from the editorial of that problem (do check it, I didn't look at it into detail), it proves a solution that uses matrix exp of a square matrix of size O(N), that means that there's a recurrence with O(N) terms. What happens often in these problems is that sometimes we have extra states that can be simplified by merging different states into the same thing.
Thanks for your reply!
But I think sometime extra state will increase the number of terms of recurrence since we split one state into more states, which result in a more complicate recurrence relation.(Like in this problem, editorial use a $$$200$$$ times $$$200$$$ transition matrix, so it will have at most 200 terms, but my solution said there are some linear recurrence have about 350 terms)
my submission that compute first 500 terms got WA
my submission that compute first 700 terms got AC
I'm looking at the editorial rn, it uses 400 times 400 transition matrix. "The combined automaton should have |s| - 1 red, ⌈|s| / 2⌉ green and ⌈|s| / 2⌉ blue vertices."
You are right, it is 400 times 400.I misread the code :/