P5487 [Template] Berlekamp–Massey Algorithm

Prerequisite skills: linear recurrence and the $\&~\rm BM$ algorithm. Also, please pay attention to optimizing your memory usage. The shortest recurrence is guaranteed to be **unique**. The problem setter apologizes for forcing two tasks into one, but this is also a chance to learn the $k^2 \log n$ method for linear recurrences. It is guaranteed to pass under the `-O2` option.

You are given the first $n$ terms of a sequence $P$ starting from index $0$. Find the shortest linear recurrence of sequence $P$ modulo $998244353$, and output $P_m$ modulo $998244353$.

The first line contains two integers $n,m$, meaning that the first $n$ terms of sequence $P$ will be given, and you need to compute $P_m$. The second line contains $n$ integers, which are $P_0,P_1,P_2,\ldots,P_{n-1}$.

On the first line, output the shortest linear recurrence. On the second line, output the value of $P_m$.

For $100\%$ of the testdata, $n < m \le 10^9$, $1 \le n \le 10000$, and the length of the recurrence is guaranteed to be at most $5000$. Translated by ChatGPT 5