题解：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;
}