Bostan-mori 算法和 LSB-first 算法学习笔记

前几天 jijidawang 在赛时写的科技，oiwiki 上都没有，赶紧学习了一下。

已知 $A_n=\sum_{i=1}^kF_iA_{n-i}$，求 $A_n$。

显然该式子可以用矩阵乘法优化，但是线性递推用矩阵乘法还是太慢了，居然有高达 $O(k^3\log n)$ 的复杂度，并且就算用对于 OI 几乎为负优化的一些理论更快的矩阵乘法，也还是更慢了一些。

那这时候有人就要问了：主播主播，还有没有更快的线性递推的方法？

有的兄弟，有的，比他更快的方法当然是有的啦。接下来，主播要隆重介绍一下 LSB-first 算法。

## Bostan-mori 算法

如何求解 $\left[x^n\right]\frac{f(x)}{g(x)}$ 呢？

我们可以仿照一下 FFT 的思路，把上面的拆成 $f(x)$ 奇次项和偶次项。

但关键问题是下面的 $g(x)$ 可能并不都是偶次项，直接拆肯定是不对的。

考虑把 $g(x)$ 中的所有奇次项消掉，直接上下同乘一个 $g(-x)$ 就好了。

$$\left[x^n\right]\frac{f(x)}{g(x)}=\left[x^n\right]\frac{f(x)g(-x)}{g(x)g(-x)}=\left[x^n\right]\frac{f_0(x^2)+xf_1(x^2)}{g'(x^2)}=\begin{cases}
\left[x^{\frac{n}{2}}\right]\frac{f_0(x)}{g'(x)}&n\bmod2=0\\
\left[x^{\frac{n-1}{2}}\right]\frac{f_1(x)}{g'(x)}&n\bmod2=1
\end{cases}$$

直接递归下去即可。最终可以递归到 $\left[x^0\right]\frac{F(x)}{G(x)}$，直接计算 $\frac{F\left[0\right]}{G\left[0\right]}$ 就行啦，设 $f$ 和 $g$ 项数都是 $O(k)$ 级别的，用上 NTT，时间复杂度为 $O(k\log k\log n)$。

那这时候又有人要问了：主播主播，你不是要推荐 LSB-first 算法吗？为什么在讲波斯坦-茉莉？

兄弟们，刚才是前置知识，现在才是正题。

## LSB-first 算法

我们可以想方设法地把求 $A_n$ 的问题转换成求形如 $\left[x^n\right]\frac{f(x)}{g(x)}$ 的问题。

我们可以继续使用生成函数的知识：设 $Q(x)=\sum_{n\ge0}A_nx^n$，$P(x)=\sum_{i=1}^{k}F_ix^i$，$R(x)=\sum_{i=0}^{k-1}a_ix^i$。由递推式子，可得 $Q(x)=\sum_{i=1}^{k}F_ix^iQ(x)+\sum_{i=0}^{k-1}a_ix^i-\sum_{i=1}^{k-1}\sum_{j=0}^{i-1}A_iF_{i-j}$。

则 $(1-P(x))Q(x)=R(x)-\sum_{i=1}^{k-1}\sum_{j=0}^{i-1}A_iF_{i-j}$。

发现后面的式子相当于 $R(x)-R(x)P(x)$，但是最高次项仅为 $k-1$，$\ge k$ 的项不存在。

然后一除，不就完了吗？

然后你就可以切掉[P4723 【模板】常系数齐次线性递推](https://www.luogu.com.cn/problem/P4723) 啦。

封装类的[在这里](https://www.luogu.com.cn/paste/8gr09umt)，以下仅展示关键部分代码：

```cpp
const int mod=998244353; 
using poly = POLY::Poly<int>;
int Bostan(poly F,poly G,int k){
	for(int i;k;k>>=1){
		poly R=G;
		for(i=1;i<R.len();i+=2)R[i]=mod-R[i];//g(-x)
		F*=R,G*=R;
		for(i=k&1;i<F.len();i+=2)F[i>>1]=F[i];F.Resize(i>>1); 
		for(i=0;i<G.len();i+=2)G[i>>1]=G[i];G.Resize(i>>1);
	}
	return (!F.len())?0:F[0]*quick_pow(G[0],mod-2)%mod;
}
int LST_first(poly F,poly A,int n){
	poly f(1);f[0]=1;
	F=f-F;f=A*F;//多项式-*不说了
	f=f.cut(A.len());//只截取前 k 项
	return Bostan(f,F,n);
}
int n,k;
signed main(){ 
    scanf("%lld%lld",&n,&k);
    poly F(k+1),A(k);F[0]=0;
    for(int i=1,x;i<=k;++i)scanf("%lld",&x),F[i]=(x%mod+mod)%mod;
	for(int i=0,x;i<k;++i)scanf("%lld",&x),A[i]=(x%mod+mod)%mod;
	printf("%lld\n",LST_first(F,A,n));
	return 0;
}
```

例题：目前没有，欢迎推荐。

正在渲染内容...