倍增FFT

已知关于 $x​$ 的多项式 $\prod_{i=1}^k (x+i)​$ 的各项系数,欲求 $\prod_{i=k+1}^{2k} (x+i)​$ 的各项系数.

做法

记 $F(x)=\prod_{i=1}^k (x+i)=\sum_{i=0}^k c_i\cdot x^i, G(x)=\prod_{i=k+1}^{2k} (x+i)$ ,则

$$\begin{aligned} G(x)&=F(x+k) \\ &=\sum_{i=0}^k c_i\cdot (x+k)^i \\ &=\sum_{i=0}^k c_i\cdot \sum_{j=0}^i \binom i j k^{i-j}x^j \\ &=\sum_{j=0}^k \frac {k^{-j}} {j!}\cdot x^j\cdot \sum_{i=j}^k (c_i\cdot k^i\cdot i!)\cdot \frac 1 {(i-j)!} \end{aligned}$$ 对着系数稍微构造一下向量 $a,b$ 就可以得到
$$G(x)=\sum_{j=0}^k \frac {k^{-j}} {j!}\cdot x^j\cdot \sum_{i=0}^{2k} a_i\cdot b_{j+k-i}$$ 于是对 $a,b$ 做一次卷积即可算出 $G(x)$ 的各项系数,时间复杂度 $O(k\log k)$ .

应用

求多项式 $F(x)=\prod_{i=1}^n (x+i)$ 的各项系数.

若直接用分治 FFT 求解, 时间复杂度 $O(n\log^2 n)$ .

考虑像快速幂那样倍增去做,记 $m=\lfloor \frac{n}{2}\rfloor$ .

先求出 $\prod_{i=1}^m (x+i)​$ 的各项系数,用上面的做法 $O(m\log m)​$ 推出 $\prod_{i=m+1}^{2m} (x+i)​$ 的各项系数.

$O(m\log m)$ 将它们乘起来得到 $\prod_{i=1}^{2m} (x+i)$ 的各项系数,若 $n$ 为奇数,再暴力乘上 $(x+n)$ 这个单项式.

时间复杂度 $T(n)=T(\frac n 2)+O(n\log n) = O(n\log n)$ .