载谭 Binomial Sum 学习笔记

对于微分有限的生成函数 \(F(x)\)，有一个生成函数 \(G(x)\)，以及数列 \(a\)，如果对于 \(0 \le k \le n\)，我们已知 \(\displaystyle \sum_{i=0}^n a_i [x^i] G(x)^k\)，那么我们能够在 \(\Theta(n)\) 的时间复杂度内求出 \(\displaystyle \sum_{i=0}^n a_i[x^i]F(G(x))\)。

设 \(c=[x^0]G(x)\)，考虑 \(F\) 在 \(c\) 处的泰勒展开，则 \(\displaystyle F(G(x))=\sum_{k\ge 0} F^{(k)}(c)\frac{{(G(x)-c)}^k}{k!}\)，由于 \(G(x)-c\) 的常数项为 \(0\)，我们只关心结果在 \(\bmod{x^{n+1}}\) 意义下的值，所以此处 \(k\) 只需枚举到 \(n\) 即可。

设 \(F(x)\) 所满足的微分方程为 \(\displaystyle \sum_{i=0}^m p_i(x)F^{(i)}(x)=0\)，则 \(\displaystyle \sum_{i=0}^m p_i(x+c)F^{(i)}(x+c)\)，这里我们将 \(m\) 看作常数。

对 \(F(x+c)\) 截取其前 \(n+1\) 项，设生成函数 \(\mathcal{F}(x+c)=F(x+c)\pmod{x^{n+1}}\)。

而考虑 \(\displaystyle \sum_{i=0}^m p_i(x)\mathcal{F}^{(i)}(x)\)，当且仅当从 \(\le n\) 的项贡献到 \(>n\) 的项时会出现问题，于是设 \(\displaystyle \sum_{i=0}^m p_i(x)\mathcal{F}^{(i)}(x)=\mathcal{D}(x)\)，根据方程进行递推即可。