已知关于 $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)$ .