[x^n]g(x)f(x)^k for k in [0,m]

· · 算法·理论

update：完善了一下情况 3 的做法。

我们经常能遇到这样一类经典问题：

对 k=0,1,\cdots,m 求 a_k=[x^n]g(x)f(x)^k

其中 g(x),f(x) 一般具有简单的封闭形式，下面分情况整理一下做法。
以下定义 \operatorname{ord}F(x) 为 F(x) 的最低非零项的次数。

最简单的一种情况，设 h(x)=f^{\langle -1 \rangle}(x)，应用另类 Lagrange 反演就有：

a_k=[x^{n-k}]g(h(x))h'(x)\left( \frac{x}{h(x)}\right)^{n+1}

设 d=\operatorname{ord}f(x)，c=[x^d]f(x)。再设 F(x)=\sqrt[d]{f(x)/c}，则：

a_k=c^k[x^n]g(x)F(x)^{dk}

就可以按照情况 1 的方法直接求解。

设常数项为 c，F(x)=f(x)-c，若 \operatorname{ord}F(x)=1，可以设 h(x)=F^{\langle -1 \rangle}(x)：

a_k=[x^n]g(x)(F(x)+c)^k =[x^n]g(h(x))(x+c)^kh'(x) \left( \frac{x}{h(x)}\right)^{n+1}

这样把原问题就可以简化为 f(x)=x+c 的情况（但 g(x) 可能不再有简单的封闭形式）：

b_k=[x^n]g(x)(x+c)^k=\sum_{i=0}^k \binom ki g_{n-i}c^{k-i}

也就是算出 g(x) \bmod x^{n+1} 后再翻转系数，就可以直接卷积计算了。

如果 \operatorname{ord}F(x)>1，也可以类比情况 2 的处理方法，把问题化简为 f(x)=x^d+c 的情况。

只需注意到 f(x) 的乘法逆就是形式幂级数，设 F(x)=f(x)^{-1}，则：

a_k=[x^n]g(x)F(x)^{-k}

若 F(x) 的一次项非零，可以设其复合逆为 h(x)，则：

a_k=[x^{n+k}]g(h(x))h'(x)\left( \frac{x}{h(x)}\right)^{n+1}

若 \operatorname{ord}F(x)>1 ，类比一下情况 2 即可。

最后，如果 f(x) 是代数幂级数，且 g(x) 是微分有限的，那么 a_k 显然可以整式递推计算。不过这是 ODE 自动机的事了，不是我的事（