其实是用于常系数齐次线性递推，只不过本篇博文只讲解如何求分式的高次项系数。
已知多项式 \(f(x),g(x)\)，要求：\([x^k]\dfrac{f(x)}{g(x)}\)，其中 \(f(x),g(x)\) 的次数为 \(n,m\)，\(n,m\le 10^5,k\le 10^9\)。
算法流程如下：
分式上下同乘 \(g(-x)\)，也就是 \(g\) 的奇次项都取反的多项式，得到：
\[[x^k]\dfrac{f(x)}{g(x)}=[x^k]\dfrac{f(x)g(-x)}{g(x)g(-x)} \]分母部分一个重要的性质是，由于奇次项系数为相反数，那么最终卷积的结果奇次项都为 \(0\)，所以 \(g(x)g(-x)=H(x^2)\)，把 \(f(x)g(-x)\) 奇偶分类，变成 \(f(x)g(-x)=F(x^2)+xG(x^2)\)，这样可以得到：
\[[x^k]\dfrac{f(x)}{g(x)}=[x^k]\dfrac{f(x)g(-x)}{g(x)g(-x)}=[x^k]\dfrac{F(x^2)+xG(x^2)}{H(x^2)} \]注意到 \([x^k]\) 只会由分子中某个多项式贡献而来，之后上下的自变量就可以由 \(x^2\) 变为 \(x\)，具体地：
\[[x^k]\dfrac{f(x)}{g(x)}=[x^k]\dfrac{f(x)g(-x)}{g(x)g(-x)}=[x^k]\dfrac{F(x^2)+xG(x^2)}{H(x^2)}= \begin{cases} [x^{\lfloor k/2\rfloor}]\dfrac{F(x)}{H(x)}&k\mid 2\\ [x^{\lfloor k/2\rfloor}]\dfrac{G(x)}{H(x)}&k\not\mid 2 \end{cases}\]每次减半，最终 \(k=0\) 时输出常数项的结果即可。注意到每次卷积规模扩大后只取一半系数使规模减小，所以复杂度 \(O(n\log n\log k)\)。
inline void Bostan_Mori(int N,Poly F,Poly G){
int L=F.deg;
Poly H,A,B;
F.set(L<<1),G.set(L<<1),H.set(L<<1),A.set(L<<1),B.set(L<<1);
while(N){
H=G;
for(int i=1;i<L;i+=2) H[i]=mod-H[i];
F.NTT(L<<1,1),G.NTT(L<<1,1),H.NTT(L<<1,1);
for(int i=0;i<L<<1;++i) A[i]=F[i]*H[i]%mod,B[i]=G[i]*H[i]%mod;
A.NTT(L<<1,0),B.NTT(L<<1,0);
for(int i=0;i<L;++i) B[i]=B[i*2];
for(int i=0;i<L;++i) A[i]=A[2*i+(N&1)];
A.clear(L,(L<<1)-1),B.clear(L,(L<<1)-1);
F=A,G=B;
N>>=1;
}
printf("%llu\n",F[0]*q_pow((int)G[0],mod-2,mod)%mod);
}