[x^n]g(x)f(x)^k for k in [0,m]
NaCly_Fish
2022-09-27 19:09:28
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)$ 的最低非零项的次数。
1. $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}$$
2. $f(x)$ 没有负次项,$\operatorname{ord} f(x)>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 的方法直接求解。
3. $f(x)$ 没有负次项,常数项非零。
设常数项为 $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$ 的情况。
4. $f(x)$ 为有负次项的形式 Laurent 级数。
只需注意到 $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 自动机的事了,不是我的事(