这里所有的内容都将有关于一个线性递推：
$f_{n} = \sum\limits_{i = 1}^{k} a_{i} * f_{n - i}$，其中$f_{0}, f_{1}, ... , f_{k - 1}$是已知的。
BM是用于求解线性递推式的工具，传入一个序列，会返回一个合法的线性递推式，一个$vector$，其中第$i$项表示上式的$a_{i + 1}$。
CH用于快速求解常系数齐次线性递推的第$n$项，我们先会求出一个特征多项式$g$，$g$的第$k$项是$1$，其余项中第$k - i$项是$-a_{i}$。然后可以得到$c = x^{n} \; mod \; g$这么一个多项式，最后的答案就是$\sum\limits_{i = 0}^{k - 1} c_{i} * f_{i}$，这里用$c_{i}$表示$c$中第$i$项的系数。
其实这里只是想给出两者的板子，素质二连：
namespace BM{
#define pb push_back
#define SZ(x) ((int)x.size())
#define REP(i, a, b) for (int i = a; i < b; ++i)
LL Pow(LL x, LL b) {
LL re = ;
x %= MOD, assert(b >= );
for (; b; b >>= , x = x * x % MOD)
if (b & ) re = re * x % MOD;
return re;
}
VI Bm(VI x) {
VI ls, cur;
int pn = , lf, ld;
REP(i, , SZ(x)) {
LL t = -x[i] % MOD;
REP(j, , SZ(cur))
t = (t + x[i - j - ] * (LL)cur[j]) % MOD;
if (!t) continue;
if (cur.empty()) {
cur.resize(i + );
lf = i, ld = t;
continue;
}
LL k = -t * Pow(ld, MOD - ) % MOD;
VI c(i - lf - );
c.pb(-k);
REP(j, , SZ(ls)) c.pb(ls[j] * k % MOD);
if (c.size() < cur.size())
c.resize(cur.size());
REP(j, , SZ(cur))
c[j] = (c[j] + cur[j]) % MOD;
if (i - lf + SZ(ls) >= SZ(cur))
ls = cur, lf = i, ld = t;
cur = c;
}
VI &o = cur;
REP(i, , SZ(o))
o[i] = (o[i] % MOD + MOD) % MOD;
return o;
}
}
namespace CH {
#define SZ(x) ((int)x.size())
VI g;
int k;
inline void Ad(int &a, int b) {
if ((a += b) >= MOD) a -= MOD;
}
VI Mul(VI a, VI b) {
VI c;
assert(SZ(a) <= k && SZ(b) <= k);
c.resize(SZ(a) + SZ(b) - );
for (int i = ; i < SZ(a); ++i)
for (int j = ; j < SZ(b); ++j)
Ad(c[i + j], (LL)a[i] * b[j] % MOD);
for (int i = SZ(c) - ; i >= k; --i)
for (int j = ; j <= k; ++j)
Ad(c[i - k + j], MOD - (LL)c[i] * g[j] % MOD);
c.resize(k);
return c;
}
VI Solve(VI a, int n) {
k = SZ(a);
g.resize(k + , );
for (int i = ; i <= k; ++i)
g[k - i] = (MOD - a[i - ]) % MOD;
VI re(, ), x(, );
x[] = ;
for (; n; n >>= , x = Mul(x, x))
if (n & ) re = Mul(re, x);
return re;
}
}