线性递推
我们说明,如果一个生成函数 $\frac{P\left(x\right)}{Q\left(x\right)}$,满足 $\deg\left(P\left(x\right)\right) < \deg\left(Q\left(x\right)\right)$,那么,该封闭形式所对应的原函数 $A\left(x\right)$ 是一个 $\deg\left(Q\left(x\right)\right)$ 阶递推。
为了方便描述,令 $d = \deg\left(Q\left(x\right)\right)$。
由于定义,对于 $i \geq d$ 有 $a_i = \sum\limits_{j = 1}^dc_ja_{i - j}$。
构造 $Q\left(x\right) = 1 - \sum\limits_{i = 1}^dc_ix^i$,设 $P\left(x\right) = Q\left(x\right)A\left(x\right)$,那对于 $i \geq d$ 我们有
$$p_i = \sum\limits_{j = 0}^dq_ja_{i - j} = a_i - \sum\limits_{j = 1}^dc_ja_{i - j} = 0$$
因此 $\deg\left(P\left(x\right)\right) \leq d - 1$。由于 $q_0 = 1$,$Q\left(x\right)$ 有逆 $Q^{-1}\left(x\right)$,对 $P\left(x\right) = Q\left(x\right)A\left(x\right)$ 两边同时乘上 $Q^{-1}\left(x\right)$,得到 $\frac{P\left(x\right)}{Q\left(x\right)} = A\left(x\right)$
同样的,在 $\frac{P\left(x\right)}{Q\left(x\right)} = A\left(x\right)$ 两边乘上 $Q\left(x\right)$,得到 $A\left(x\right)Q\left(x\right) = P\left(x\right)$,考虑 $i \geq d$ 的 $p_i$:
$$p_i = 0 = a_i - \sum\limits_{j = 1}^dc_ja_{i - j} = \sum\limits_{j = 0}^dc_ja_{i - j}$$
因此 $\left(a_n\right)_{n \geq 0}$ 是 $d$ 阶线性递推。
Bostan-Mori
假设我们要求 $a_k$。
若 $k = 0$,由于 $P\left(x\right) = A\left(x\right)Q\left(x\right)$,所以 $p_0 = a_0q_0 = a_0 = P\left(0\right)$。
对于 $k \geq 1$:
把生成函数变成 $\frac{P\left(x\right)Q\left(-x\right)}{Q\left(x\right)Q\left(-x\right)}$ 的形式。
考虑 $\left[x^t\right]Q\left(x\right)Q\left(-x\right) = \sum\limits_{i + j = t, j is even}q_iq_j + \sum\limits_{i + j = t, j is odd}q_i\left(-q_j\right) = 0$,于是我们只需要考虑它的偶数次项,存在 $V\left(x^2\right) = Q\left(x\right)Q\left(-x\right)$。
我们设 $U\left(x\right) = P\left(x\right)Q\left(-x\right)$,现在我们把 $U\left(x\right)$ 分成两个多项式,一个只有奇数次项,一个只有偶数次项:
$$U_e\left(x\right) = \sum\limits_{i = 0}^{d - 1}u_{2i}x^i$$
$$U_o\left(x\right) = \sum\limits_{i = 0}^{d - 1}u_{2i + 1}x^i$$
$$U\left(x\right) = U_e\left(x^2\right) + xU_o\left(x^2\right)$$
$x^k$ 项系数只会由 $U_e\left(x^2\right)$ 或 $U_o\left(x^2\right)$ 贡献而来。于是
$$ \left[x^k\right]\frac{U\left(x^2\right)}{V\left(x^2\right)} = \begin{cases} \left[x^k\right]\frac{U_e\left(x\right)}{V\left(x^2\right)} & k\text{ is even} \\ \left[x^k\right]\frac{U_o\left(x^2\right)}{V\left(x^2\right)} & k\text{ is odd} \end{cases} = \begin{cases} \left[x^{k / 2}\right]\frac{U_e\left(x\right)}{V\left(x\right)} & k\text{ is even} \\ \left[x^{(k - 1) / 2}\right]\frac{U_o\left(x\right)}{V\left(x\right)} & k\text{ is odd} \end{cases} $$
若使用 FFT 处理多项式乘法,则计算量为 $O\left(d \log d \log k\right)$。
代码
lib::mint Bostan_Mori(lib::poly P, lib::poly Q, tp k) {
while (k != 0) {
auto nQ = Q;
for (tp i = 1; i < Q.size(); i += 2) nQ[i] = -nQ[i];
auto U = P * nQ;
P.clear();
for (tp i = k % 2; i < U.size(); i += 2) P.push_back(U[i]);
auto sQ = Q * nQ;
Q.clear();
for (tp i = 0; i < sQ.size(); i += 2) Q.push_back(sQ[i]);
k >>= 1;
}
return P[0] / Q[0];
}
hhhqx · 2025-02-04 18:25
%%%