例
设 \(g = ax^2 + bx + c\)，求：
\[
f = g^n\]
其中 \(0 \leq n \leq 3 \times 10^5\)。结果对 \(10^9 + 7\) 取模。
首先可以直接用 MTT 在 \(O(n \log n)\) 的时间复杂度内求解。然而此做法常数太大，在需要多次求解时效率低下。这里我们介绍一种能在 \(O(n)\) 时间复杂度内求解问题的较小常数解法。
考虑对原式求导。根据复合函数求导法则：
\[
(f(g(x)))' = f'(g(x)) g'(x)\]
有：
\[
f' = n g^{n-1} g'\]
由于：
\[
g^{n-1} = \frac{f}{g}\]
所以：
\[
f' = n \frac{f}{g} g'\]
\[
f' g = n f g'\]
\[
[x^k] f' g = [x^k] n f g'\]
\[f'_k g_0 + f'_{k-1} g_1 + f'_{k-2} g_2 = n (f_k g'_0 + f_{k-1} g'_1)\]
\[
(k+1) f_{k+1} g_0 + k f_k g_1 + (k-1) f_{k-1} g_2 = n f_k g'_0 + n f_{k-1} g'_1\]
\[
f_{k+1} = \frac{n f_k g'_0 + n f_{k-1} g'_1 - k f_k g_1 - (k-1) f_{k-1} g_2}{(k+1)g_0}\]
先求出边界 \(f_0 = g_0^n\)，然后就可以递推了。预处理 \(k+1,g_0\) 的逆元，时间复杂度为 \(O(n)\)，常数比 MTT 小很多。