BM算法模板

有一个序列(a[1..n])，求最短的(f[1..len])，使得：
(forall i>len,sum_{j=1}^{len} f[j]*a[i-j]=a[i])

假设已经求出了(a[1..i-1])的最短递推式(f)

设(∆=a[i]-sum_{j=1}^{len} f[j]*a[i-j])

当(∆=0)时，显然(f)可以作为(a[1..i])的递推式，continue

当(∆≠0)时，我们想要找到一个递推式(g)，使得(g)代入(i)是1，(g)代入(1..i-1)是0，这样：
新的(f'=f+g*∆)

考虑之前有一次失配，递推式(h0)在(fail)处失配了，当时的(∆)是(∆')。
令(h=h0*x^{i-fail})，不难发现，
1.(h代入i的值=h0代入fail)的值，
2.(h代入i-j(j>0)的值=h0代入fail-j的值=0)

那么再使(h[i]=-h[i],h[i-fail]++)

则(h)代入(i)的值=(∆')，代入(i-j(j>0))的值(=0)

那么(f'=f+h*∆/∆')

(h)的长度是(i-fail+|h0|)，所以动态维护(i-fail)最小的失配的(f)作为(h0)即可

实现需要注意的细节：
1.当第一次遇到一个≠0的数时，len才赋值1，需特判
2.记得更新fail
3.滚动优化空间，实现见代码

---

模板题：https://www.luogu.com.cn/problem/P5487
Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;

const int mo = 998244353;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

const int N = 10005;

namespace sub1 {
	ll f[3][N], dta[3];
	int len[3], fail[3];
	void cp(int x, int y) {
		len[y] = len[x]; fail[y] = fail[x]; dta[y] = dta[x];
		fo(i, 1, len[x]) f[y][i] = f[x][i];
	}
	void build(ll *a, int n) {
		fo(i, 0, n) {
			ll d = a[i];
			fo(j, 1, len[0]) d = (d - f[0][j] * a[i - j]) % mo;
			dta[0] = d;
			if(!d) continue;
			fail[0] = i;
			if(!len[0]) {
				cp(0, 1); len[0] = 1;
				continue;
			}
			cp(0, 2);
			ll c = dta[0] * ksm(dta[1], mo - 2) % mo;
			int st = i - fail[1]; len[0] = max(len[0], st + len[1]);
			f[0][st] = (f[0][st] + c) % mo;
			fo(j, 1, len[1]) f[0][st + j] = (f[0][st + j] - c * f[1][j]) % mo;
			if(len[2] - fail[2] < len[1] - fail[1]) cp(2, 1);
		}
	}
}

int n, m; ll a[N];

ll f[N]; int len;

ll x[N], s[N], c[N];

void cheng(ll *a, ll *b) {
	fo(i, 0, 2 * len) c[i] = 0;
	fo(i, 0, len) fo(j, 0, len)
		c[i + j ] = (c[i + j] + a[i] * b[j]) % mo;
	fo(i, 0, 2 * len) a[i] = c[i];
	fd(i, 2 * len, len + 1)	{
		ll v = a[i]; int st = i - (len + 1);
		fo(j, 1, len) a[st + j] = (a[st + j] - v * f[j]) % mo;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	fo(i, 1, n) scanf("%lld", &a[i]);
	sub1 :: build(a, n);
	
	len = sub1 :: len[0];
	fo(i, 1, len) f[i] = sub1 :: f[0][i];
	
	fo(i, 1, len) {
		f[i] = (f[i] % mo + mo) % mo;
		pp("%lld ", f[i]);
	}
	hh;
	
	reverse(f + 1, f + len + 1);
	fo(i, 1, len) f[i] = -f[i]; f[len + 1] = 1;
	
	x[1] = 1; s[0] = 1;
	for(m ++; m; m /= 2, cheng(x, x)) 
		if(m & 1) cheng(s, x);
		
	ll ans = 0;
	fo(i, 1, len) ans = (ans + s[i] * a[i]) % mo;
	pp("%lld
", (ans % mo + mo) % mo);
}