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](https://mirror.codeforces.com/blog/entry/96199#comment-903177))↵
↵
<spoiler summary="simple description">↵
According to Cayley-Hamilton theorem, the power of a $n$ times $n$ matrix can be seen as a linear recurrence have atmost $n$ terms, so let say we have some $dp[n][m]$ which every $dp[i]$ is a $n$ times $1$ vector, and we can get $dp[i]$ from the previous $dp[j] (j < i)$ by multiplying a transition matrix $A_{n \times n}$, then we can manipulate Cayley-Hamilton theorem like below to get a linear recurrence of a certain entries of $dp[i]$, then brute-force the first $2n$ terms of $dp[i] (i \leq 2n)$, plug all of them into Berlekamp-Massey, and we will get the actual recurrence relation of a certain entries of $dp[i]$, finally compute the k-th term of linear recurrence in $O(n^2lgk)$ or $O(nlgnlgk)$ using FFT.↵
↵
($A$ is a $n$ times $n$ matrix, $b_i$ is a $n$ times $1$ vector whose entry are all $0$ except i-th row is $1$)↵
$$ $$↵
$$A^{m} = \sum_{j = 1}^{n}c_j A^{m - j}$$↵
$$ $$↵
$$A^{m}dp[0] = \sum_{j = 1}^{n}c_j A^{m - j}dp[0] = dp[m]$$↵
$$ $$↵
$$b_i^TA^{m}dp[0] = \sum_{j = 1}^{n}c_j b_i^TA^{m - j}dp[0] = b^T_idp[m] = dp[m][i]$$↵
$$ $$↵
$$\sum_{j = 1}^{n}c_j dp[m - j][i]= dp[m][i]$$↵
$$ $$↵
</spoiler>↵
↵
And the question arise when I encounter this problem [506E — Mr. Kitayuta's Gift](https://mirror.codeforces.com/contest/506/problem/E), I write a dp solution below.↵
↵
<spoiler summary="Spoiler">↵
Assume we will construct a palidrome $S$ of length $n + |s|$, then we can just build the left half of the string then the rest will be fixed.↵
↵
To make sure $S$ contain $s$ as a subsequence, we can maintain two position $L, R$ which means $s[i](L \le i \le R)$ have not been inserted to string $S$, when we add a letter $X$ at the end of $S$, if $X = s[L]$, then we let $L$ become $L + 1$(because we already add $s[L]$ to $S$, if $X = s[R]$, then we let $R$ become $R - 1$.↵
↵
So we can get the following dp solution.↵
↵
$dp[i][L][R]$ store the number of string have length $i$, and $s[j](L \le j \le R)$ have not been inserted to the string.↵
then we will have the following transition.↵
↵
\begin{equation}↵
dp[i][L][R] \mathrel{+}=↵
\begin{cases}↵
dp[i-1][L][R] & \text{if } L = R + 1 \text{ or } (s[L] \neq j \text{ and } s[R] \neq j)\\\\↵
dp[i-1][L-1][R] & \text{if } s[L-1] = j \text{ and } (s[R] \neq j \text{ or } L = R + 1)\\\\↵
dp[i-1][L][R + 1] & \text{if } s[R + 1] = j \text{ and } (s[L] \neq j \text{ or } L = R + 1)\\\\↵
dp[i-1][L-1][R + 1] & \text{if } s[L-1] = s[R + 1] = j↵
\end{cases} ↵
\end{equation}↵
↵
time complexity: $O(26(n + |s|)|s|^2)$↵
</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](https://mirror.codeforces.com/contest/506/submission/153367961).↵
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.
↵
<spoiler summary="simple description">↵
According to Cayley-Hamilton theorem, the power of a $n$ times $n$ matrix can be seen as a linear recurrence have atmost $n$ terms, so let say we have some $dp[n][m]$ which every $dp[i]$ is a $n$ times $1$ vector, and we can get $dp[i]$ from the previous $dp[j] (j < i)$ by multiplying a transition matrix $A_{n \times n}$, then we can manipulate Cayley-Hamilton theorem like below to get a linear recurrence of a certain entries of $dp[i]$, then brute-force the first $2n$ terms of $dp[i] (i \leq 2n)$, plug all of them into Berlekamp-Massey, and we will get the actual recurrence relation of a certain entries of $dp[i]$, finally compute the k-th term of linear recurrence in $O(n^2lgk)$ or $O(nlgnlgk)$ using FFT.↵
↵
($A$ is a $n$ times $n$ matrix, $b_i$ is a $n$ times $1$ vector whose entry are all $0$ except i-th row is $1$)↵
$$ $$↵
$$A^{m} = \sum_{j = 1}^{n}c_j A^{m - j}$$↵
$$ $$↵
$$A^{m}dp[0] = \sum_{j = 1}^{n}c_j A^{m - j}dp[0] = dp[m]$$↵
$$ $$↵
$$b_i^TA^{m}dp[0] = \sum_{j = 1}^{n}c_j b_i^TA^{m - j}dp[0] = b^T_idp[m] = dp[m][i]$$↵
$$ $$↵
$$\sum_{j = 1}^{n}c_j dp[m - j][i]= dp[m][i]$$↵
$$ $$↵
</spoiler>↵
↵
And the question arise when I encounter this problem [506E — Mr. Kitayuta's Gift](https://mirror.codeforces.com/contest/506/problem/E), I write a dp solution below.↵
↵
<spoiler summary="Spoiler">↵
Assume we will construct a palidrome $S$ of length $n + |s|$, then we can just build the left half of the string then the rest will be fixed.↵
↵
To make sure $S$ contain $s$ as a subsequence, we can maintain two position $L, R$ which means $s[i](L \le i \le R)$ have not been inserted to string $S$, when we add a letter $X$ at the end of $S$, if $X = s[L]$, then we let $L$ become $L + 1$(because we already add $s[L]$ to $S$, if $X = s[R]$, then we let $R$ become $R - 1$.↵
↵
So we can get the following dp solution.↵
↵
$dp[i][L][R]$ store the number of string have length $i$, and $s[j](L \le j \le R)$ have not been inserted to the string.↵
then we will have the following transition.↵
↵
\begin{equation}↵
dp[i][L][R] \mathrel{+}=↵
\begin{cases}↵
dp[i-1][L][R] & \text{if } L = R + 1 \text{ or } (s[L] \neq j \text{ and } s[R] \neq j)\\\\↵
dp[i-1][L-1][R] & \text{if } s[L-1] = j \text{ and } (s[R] \neq j \text{ or } L = R + 1)\\\\↵
dp[i-1][L][R + 1] & \text{if } s[R + 1] = j \text{ and } (s[L] \neq j \text{ or } L = R + 1)\\\\↵
dp[i-1][L-1][R + 1] & \text{if } s[L-1] = s[R + 1] = j↵
\end{cases} ↵
\end{equation}↵
↵
time complexity: $O(26(n + |s|)|s|^2)$↵
</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](https://mirror.codeforces.com/contest/506/submission/153367961).↵
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.
