from EI
基本就是复述一遍，仅供参考。
\[\]考虑如下问题：
对于一生成函数 \(G(x)\) 和一数列 \(a\)，\(\forall 0\le k\le n\) 已知
\[\sum_{i=0}^na_i[x^i]G(x)^k \]给出另一生成函数 \(F(x)\)，求
\[\sum_{i=0}^na_i[x^i]F(G(x)) \]
若 \(F(x)\) 微分有限，并将微分方程相关视为常数，则我们可以做到 \(O(n)\) 的复杂度。
设 \([x^0]G(x)=c\)，\(F(x)\) 满足的微分方程阶数为 \(r\)。
我们考虑求出一生成函数 \(H(x)\)，满足 \(H(x+c)\equiv F(x+c) \pmod{x^{n+1}}\)。
那么有：
\[\begin{align*} &\sum_{i=0}^na_i[x^i]F(G(x))\\ =&\sum_{i=0}^na_i[x^i]F(G(x)-c+c)\\ =&\sum_{i=0}^na_i[x^i]\sum_{j\ge 0}([x^j]F(x+c))(G(x)-c)^j\\ =&\sum_{i=0}^na_i[x^i]\sum_{j=0}^n([x^j]H(x+c))(G(x)-c)^j\\ =&\sum_{i=0}^na_i[x^i]H(G(x))\\ =&\sum_{i=0}^nh_i\sum_{j=0}^na_j[x^j]G(x)^i \end{align*} \]于是问题转为求 \(H(x)\)。
考虑 \(F(x)\) 满足的微分方程：
\[\sum_{i=0}^rp_i(x)F^{(i)}(x)=0 \]则：
\[\sum_{i=0}^rp_i(x+c)F^{(i)}(x+c)=0 \]考虑将 \(F\) 替换成 \(H\) 后的影响，此时我们只失去了 \(>n\) 的项，所以若某一项只与 \(\le n\) 的项有关或只与 \(>n\) 的项有关我们就不必去考虑它，唯一影响的只有在一段区间，我们设这个扰动因子为 \(D(x)\)，那么：
\[\sum_{i=0}^ip_i(x)H^{(i)}(x)=D(x-c) \]此时我们就可以递推出 \(H(x)\) 了。
现在大多数为 \(G(x)=e^x\) 的情况。
例：
-
\(\sum_{i=0}^ma_i[\frac{x^i}{i!}]e^{nx}\)
\(F(x)=x^n\)
显然有：
\[F(x)'x=nF(x) \]考察 \(x^m\) 次项，有：
\[(m+1)\binom{n}{m+1}(x-1)^m+H(x)'x=nH(x) \] -
\(\sum_{i=0}^ma_i[\frac{x^m}{k!}](1+e^x)^n\)
\(F(x)=(1+x)^n\)。
显然有：
\[F(x)'(1+x)=nF(x)\\ \]考察 \(x^m\) 项，可以得到：
\[2(m+1)\binom{n}{m+1}2^{n-m-1}(x-1)^k+H(x)'(1+x)=nH(x) \] -
\(\sum_{i=0}^m a_i[\frac{x^i}{i!}](qe^x+(1-q))^n\)
\(F(x)=(qx+(1-q))^n\)。
显然有：
\[F(x)'(x+\frac{1-q}{q})=nF(x) \]考察 \(x^m\) 次项，可以得到：
\[q^m(m+1)\binom{n}{m+1}(x-1)^m+H(x)'(x+\frac{1-q}{q})=nH(x) \]
参考资料