好像之前就学过,但是因为洛谷板子要写线性递推所以鸽了.
 今天才发现洛谷板子原来不用写多项式取模,那没事了.
 这个东西十分厉害,可以用来求解数列递推式,一般还可以得到最短的递推式.所以如果有时候的意识到答案是个线性递推式,直接把 $\text{BM}$ 拉过来,可能有奇效(
 这个东西的核心思想在于,增量地使得每次加入数列新的一项后,递推式仍然合法.
 假设现在已经得到了一个递推式,但是在 $p$ 这一项的时候,上式值为 $v\ne 0$,则现在需要修一修递
 推式.
 注意到当前的递推式,可以使得 $p$ 之前的每一个值 $=0$,唯独 $p$ 这里的值 $\ne 0$.
 假设这不是第一次我们发现这个问题了,在 $p'<p$ 的时候也遇到过,当时的值为 $v'$.那我可以直接把当时那个递推式拉过来,乘上 $\dfrac{v}{v'}$,加到当前的递推式上,由于 $p'$ 当时的递推式在 $p'$ 之前也会 $=0$,所以不会改变之前的正确性.
 如果是第一次,直接当初值(
 至于求最短递推式,直接每次考虑把哪个 $p'$ 拉过来用的时候,选择使得递推式长度最短的拿过来用就行了.
 这题还要一个线性递推,但是可以直接暴力多项式取模,做到 $\mathcal{O}(k^2\log n)$,其中 $k$ 是递推式长度.
 return cur;