题解：P4723 【模板】常系数齐次线性递推

更差的阅读体验

---

BM 部分内容参考 OI-wiki 有关部分，致谢。

Bostan-Mori 算法

求 \([x^k] \frac{P(x)}{Q(x)}\)，\(k\) 很大。

\[\begin{align} [x^k] \frac{P(x)}{Q(x)} &= [x^k] \frac{P(x) Q(-x)}{Q(x) Q(-x)}\nonumber \\ &= [x^k] \frac{F_0(x^2) + x F_1(x^2)}{G(x^2)} \nonumber \\ &= [x ^ {\lfloor k / 2 \rfloor}] \frac{F_{k \bmod 2}(x)}{G(x)} \nonumber \end{align}\]

注明一下：\(Q(x)\) 和 \(Q(-x)\) 的卷积显然为偶函数，因此仅含有偶次项，我们将其表示成 \(G(x^2)\) 的形式。而我们记 \(F(x) = P(x)Q(-x) = F_0(x^2) + x F_1(x^2)\)，其中 \(F_0, F_1\) 为 \(F\) 拆分奇偶次项的结果。

可以看到，我们将原问题变为了 \(k\) 折半的子问题。对于每个 \(k\) 我们要求解卷积，只需要两次 NTT，不难做到 \(O(n \log n \log k)\)。

参考实现在最后。

常系数齐次线性递推

求 \(a_n = \sum \limits_{i = 1} ^ k f_{i} a_{n-i}\)。

有了 Bostan-Mori 算法，我们尝试构造 \(a_n = [x^n] \frac{P(x)}{Q(x)}\)。

假设 \(A(x) = \sum_i a_i x^i\)，那么 \(A(x)Q(x) = P(x)\)。由于 \(n\) 很大，取 \(P\) 的高位我们认为是 \(0\)。

那么 \([x^n] A(x)Q(x) = 0\)。假设 \(Q\) 各项系数为 \(q\)。则有

\[\sum_{i = 0}^n a_i q_{n-i} = 0 \]

那么我们把 \(a_n\) 提取出来，等价于左右同除以 \(q_0\)，也就是

\[a_n = - \sum_{i = 0}^{n - 1} \frac{q_{n - i}}{q_0} a_i \]

同理 \(q\) 的高位我们也认为是 \(0\)，可以直接去掉。所以其实 \(i\) 是从 \(n - k\) 开始枚举，也就是

\[a_n = - \sum_{i = n - k}^{n - 1} \frac{q_{n - i}}{q_0} a_i \]

容易发现，我们构造 \(q_0 = -1, q_i = f_i\) 就可以得到题目给出的递推式子。

有了 \(Q\)，\(P\) 可以看作 \(A\) 和 \(Q\) 的卷积，一次 NTT 即可。

然后套用上述 Bostan-Mori 即可求解 \([x^n] \frac{P(x)}{Q(x)}\)。复杂度 \(O(k \log k \log n)\)。

---

我的卷积板子实现得非常古早，用数组实现的。为了防止 NTT 后原多项式中出现不可名状得数值，我直接在卷积后把两个原多项式都清空了。所以有的数组要备份很多遍，代码显得比较丑陋，凑合看罢。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
constexpr int MOD=998244353,G=3,invG=332748118;
int r[N];
int qpow(int x,int y)
{int ret=1;for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;return ret;
}
void NTT(int len,int *a,int opt)
{for(int i=0;i<len;i++)if(i<r[i])swap(a[i],a[r[i]]);for(int i=1;i<len;i<<=1){int tmp=i<<1,Wn=qpow(opt==1?G:invG,(MOD-1)/tmp);for(int j=0;j<len;j+=tmp){int w=1,x,y;for(int k=0;k<i;k++,w=1ll*w*Wn%MOD){x=a[j+k],y=1ll*w*a[i+j+k]%MOD;a[j+k]=(x+y)%MOD,a[i+j+k]=(x+MOD-y)%MOD;}}}
}
void mul(int n,int m,int *a,int *b,int *ans)
{int len=1,lg=0;while(len<n+m)len<<=1,lg++;for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<lg-1);NTT(len,a,1),NTT(len,b,1);for(int i=0;i<len;i++)a[i]=1ll*a[i]*b[i]%MOD;NTT(len,a,-1); int inv=qpow(len,MOD-2);for(int i=0;i<=len;i++)b[i]=ans[i]=0;for(int i=0;i<n+m;i++)ans[i]=1ll*a[i]*inv%MOD;for(int i=0;i<=len;i++)a[i]=0;
}
int _q[N],f[N],g[N];
int bostan_mori(int n,int m,int *p,int *q,int k)
{for(;k;k>>=1){for(int i=0;i<m;i++)_q[i]=q[i];for(int i=1;i<m;i+=2)_q[i]=(MOD-_q[i])%MOD;mul(n,m,p,_q,f);for(int i=0;i<m;i++)_q[i]=q[i];for(int i=1;i<m;i+=2)_q[i]=(MOD-_q[i])%MOD;mul(m,m,q,_q,g);int new_n=0,new_m=0;for(int i=k&1;i<n+m-1;i+=2)p[new_n++]=f[i];for(int i=0;i<m+m-1;i+=2)q[new_m++]=g[i];n=new_n,m=new_m;}if(!n||!m)return 0;return 1ll*p[0]*qpow(q[0],MOD-2)%MOD;
}
int n,k,q[N],qq[N],a[N],res[N];
main()
{scanf("%d%d",&n,&k),q[0]=qq[0]=MOD-1;for(int i=1;i<=k;i++)scanf("%d",&q[i]),qq[i]=q[i]=(q[i]%MOD+MOD)%MOD;for(int i=0;i<k;i++)scanf("%d",&a[i]),a[i]=(a[i]%MOD+MOD)%MOD;mul(k+1,k,q,a,res);for(int i=k;i<N;i++)res[i]=0;printf("%d\n",bostan_mori(k,k+1,res,qq,n));return 0;
}