初识 Bostan-Mori 求解分式远处系数 | 题解：P4723 【模板】常系数齐次线性递推

· · 题解

文化课期末考不是很愿意想题，于是来搓点科技。进场之前想着学个 BM，看了一眼 hint 上下同乘一个 Q(-x)，然后地理编完之后花了半小时编出来了，啪的一下很快啊。

给上下同乘一个 Q(-x)，变成 [x^k]\frac{P(x)Q(-x)}{Q(x)Q(-x)}。显然分母的奇数项都会抵消变成 0，这样看起来就能把问题折半了。

对 k 的奇偶性分类讨论，对于分子，我们只关心与 k 同奇偶的那些项。对于 k 为偶数，可以得到一个 \frac{F(x^2)}{G(x^2)}，对于 k 为奇数，可以得到一个 \frac{xF(x^2)}{G(x^2)}。这里 F,G 只需要计算 P(x)Q(-x) 和 Q(x)Q(-x) 就能得到。然后就能折半到 [x^{\lfloor\frac{k}{2}\rfloor}]\frac{F(x)}{G(x)} 的问题上了。继续递归即可，时间复杂度 \mathcal O(n\log n\log k)。

现在要构造 P,Q 使得 [x^n]\frac{P(x)}{Q(x)}=a_n。由于 P,Q 都得是有限次多项式，我们可以取一个 >\deg P 的次数，此时 P 对应系数为 0，再带入求解：

\sum\limits_{i=0}^{n}a_iq_{n-i}=0

把 a_nq_0 移过去除掉，得到：

a_n=-\sum\limits_{i=0}^{n-1}\frac{q_{n-i}}{q_0}a_i

那么 Q 就很容易取了：构造 q_0=1，q_i=-f_i(i\ge 1) 即可。若记 a_0,\dots,a_{n-1} 对应的多项式为 A，P 就是 Q\cdot A \bmod x^{k}。于是 P,Q 可以在 \mathcal O(k\log k) 的时间复杂度内求出，再使用 Bostan-Mori 方法即可做到 \mathcal O(k\log k\log n)。

当然有一种用特征多项式 + 多项式取模的经典做法可以做到相同复杂度，但是常数相对大很多（一轮只要两次卷积的优越性）。

ll Bostan_Mori(poly P,poly Q,ll n){// [x^n]P(x)/Q(x) 
    while(n){
        poly _Q=Q;
        for(int i=1;i<(int)Q.size();i+=2)_Q[i]=Mod-Q[i];
        P=P*_Q,Q=Q*_Q;
        int i=(n&1);
        for(;i<(int)P.size();i+=2)P[i>>1]=P[i];
        P.resize(i>>1);
        for(i=0;i<(int)Q.size();i+=2)Q[i>>1]=Q[i];
        Q.resize(i>>1),n>>=1;
    }
    if(!P.size())return 0;
    return 1ll*P[0]*pw(Q[0],Mod-2)%Mod;
}
ll Recur(ll *f,ll *a,ll T,ll n){
    poly Q;Q.resize(n+1),Q[0]=1;
    rep(i,1,n)Q[i]=Mod-f[i];
    poly R;R.resize(n);
    rep(i,0,n-1)R[i]=a[i];
    poly P=Q*R;P.resize(n);
    return Bostan_Mori(P,Q,T);
}