思路来源：penguin 学长
【题面大意】
给定多项式 \(\displaystyle f_1(x)=\sum_{i=0}^na_ix^i\) 与序列 \(\{b_n\},\{c_n\}\) 。已知递推式 \(f_n=b_nf_{n-1}‘+c_nf_{n-1}(n>1)\) ，求 \(f_n\) 。
【分析】
展开几项得到：
\(\therefore f_n=b_nf_{n-1}‘+c_nf_{n-1}\)
\(\qquad\ =b_n(b_{n-1}f‘_{n-2}+c_{n-1}f_{n-2})‘+c_n(b_{n-1}f‘_{n-2}+c_{n-1}f_{n-2})\)
\(\qquad\ =b_nb_{n-1}f^{(2)}_{n-2}+(b_nc_{n-1}+b_{n-1}c_n)f^{(1)}_{n-2}+c_nc_{n-1}f^{(0)}_{n-2}\)
\(\qquad\ =b_nb_{n-1}b_{n-3}f^{(3)}_{n-3}+(b_nb_{n-1}c_{n-2}+b_nc_{n-1}b_{n-2}+c_nb_{n-1}b_{n-2})f^{(2)}_{n-3}+(b_nc_{n-1}c_{n-2}+c_nb_{n-1}c_{n-2}+c_nc_{n-1}b_{n-2})f^{(1)}_{n-3}+c_nc_{n-1}c_{n-2}f^{(0)}_{n-3}\)
观察式子可得，系数最终与 \(\displaystyle \prod_{i=2}^n(c_ix+b_i)\) 相同。
可证明确实相同
令 \(\displaystyle D(x)=\prod_{i=2}^n(c_ix+b_i)=\sum_{i=0}^nd_ix^i\)
\(\therefore \displaystyle f_n=d_0f_1^{(n)}+d_1f_1^{(n-1)}+d_2f_1^{(n-2)}+\cdots d_nf_1^{(0)}=\sum_{i=0}^nd_{n-i}f_1^{(i)}\)
\(\therefore \displaystyle f_n[m]=\sum_{i=0}^nd_{n-i}f_1^{(i)}[m]\)
考虑 \(f^{(i)}[m]=f_1^{(i-1)}[m+1]\cdot (m+1)=\cdots =f_1[m+i]\cdot {(m+i)!\over m!}\)
故代入移项得 \(\displaystyle m!\cdot f_n[m]=\sum_{i=0}^nd_{n-i}\cdot (m+i)!\cdot f_1[m+i]\)
令 \(e_i=i!\cdot f_1[i]\)
故 \(\displaystyle m!\cdot f_n[m]=\sum_{i=0}^nd_{n-i}e_{m+i}=(D\cdot G)[n+m]\)
因此最后可以卷积求得，复杂度为 \(O(n\log n)\)
而前面的 \(D(x)\) ，可以考虑分治求解：
设前 \({n\over 2}\) 项合并，后 \({n\over 2}\) 项合并，此时合并这两项，复杂度为 \(O(n\log n)\) 。
而前后两项的合并可以递归处理，故根据主定理 \(T(n)=2T({n\over 2})+O(n\log n)\) ，可以解得复杂度为 \(O(n\log^2 n)\) 。
原文：https://www.cnblogs.com/JustinRochester/p/13705300.html