短多项式快速幂

做多校的时候碰见了这个技巧，记录下来。只能说高中的时候没有好好学生成函数，现在回看有些东西其实没有那么难的，应该认真地体系地学一下。

假设我们现在有一个 $m$ 次的多项式：

$F(x) = a_0 + a_1 x + \cdots + a_m x^m$

我们现在想求 $F^k(x)$ 的 $0$ 到 $n$ 次项系数。

在 $k$ 特别大的时候，如果我们直接用多项式快速幂模板，时间复杂度为 $O(m k \log (m k) + n)$，非常慢。但如果在 $m, n$ 都比较小的情况下，我们可以用一些技巧，让复杂度里直接不带 $k$，变为 $O(n m)$。

注意到：$F^{k + 1}(x) = F^k(x) F(x)$，两边求导得到：

$(k + 1) F^k(x) F'(x) = F^k(x) F'(x) + (F^k(x))' F(x) \\ k F^k(x) F(x) = (F^k(x))' F(x)$

用 $F[i]$ 表示多项式 $F(x)$ 的第 $i$ 次项系数，将上面的式子对比 $p$ 次项系数可得：

$k \sum_{i = 0}^p F'[i] F^k[p - i] = \sum_{i = 0}^p F[i] \cdot (p - i + 1) F^k[p - i + 1]$

将右边 $i = 0$ 的项提出来，移项可得：

$(p + 1)F[0] \cdot F^k[p + 1] = k \sum_{i = 0}^{\min\{p, m\}} F'[i] F^k[p - i] - \sum_{i = 1}^{\min\{p, m\}} F[i] \cdot (p - i + 1) F^k[p - i + 1]$

于是我们就得到了一个关于 $F^k[p]$ 的递推式，预处理 $F'[i]$ 后就可以 $O(n m)$ 时间计算出 $F^k(x)$ 的 $0$ 到 $n$ 次项系数。