纯口胡，不能保证正确性。
首先我们知道，当我们知道一个数列 \(F\) 的线性递推关系为 \(G\) 之后，假设描述为 \(F=F*G+H\)，\(|G|=k\)，那么我们可以用多项式取模或者别的方法做到 \(\mathcal (k\log k\log n)\) 及以下的，这里就不描述详述了。
然后对于不知道线性递推关系的，我们现在来考虑找到 \(F\) 的一个最短的线性递推关系。我们假设考虑了前面 \(i\) 个位置之后得到的最短合法递推关系为 \(g_i\)，通过 \(g_{i-1}\) 得到的值与 \(f_i\) 的差设为 \(\Delta _i\)。当考虑到 \(i\) 时，如果 \(\Delta _i\not=0\)，假设 \(k\) 是上一次存在误差的位置，那么我们考虑如果能构造出一个 \(Z\)，使得 \(Z\times f_{0,1,...,i-1}\) 仅在 \(f_i\) 有值，那么我们 \(g_i=g_k+K\times Z\)（\(K\) 为一个所需的常数，懂的都懂
标签：log,BM,times,胡向,算法,Delta,线性,递推 From： https://www.cnblogs.com/Dark-Romance/p/17069440.html