原文链接：载谭 Binomial Sum：多项式复合、插值与泰勒展开。
下面就从例题开始慢慢说这个算法。
P5430 [SNOI2017] 礼物 加强版
题目描述
给定 \(n, k\)，求
\[n^k+\sum_{i=1}^{n-1} 2^{n-1-i}i^k \]答案对 \(10^9+7\) 取模。
\(1 \le n \le 10^{100000}, 1 \le k \le 2\times 10^7\)。
题解
不妨将形式化得好看一些，只需要求
\[\sum_{i=0}^n a^ii^k \]其中满足 \(a \ne 1\)。
写成生成函数的形式：
\[\left[\frac{x^k}{k!}\right]\sum_{i=0}^{n} {(ae^x)}^i \]令 \(\displaystyle F(x)=\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x}\)，所求即 \(\displaystyle\left[\frac{x^k}{k!}\right]F(ae^x)\)。
\[\left[\frac{x^k}{k!}\right]F(x)\circ(ae^x)=\left[\frac{x^k}{k!}\right]F(x+a)\circ(ae^x-a) \]令 \(\mathscr{F}(x+a)=F(x+a)\bmod x^{k+1}\)，则
\[\left[\frac{x^k}{k!}\right]F(x+a)\circ (ae^x-a)=\left[\frac{x^k}{k!}\right]\mathscr{F}(x+a)\circ (ae^x-a)=\left[\frac{x^k}{k!}\right]\mathscr{F}(x)\circ (ae^x) \]\[F(x)=\frac{1-x^{n+1}}{1-x} \]\[F(x)\cdot(1-x)=1-x^{n+1} \]两边同时求导，可得
\[F(x)-F'(x)\cdot(1-x)=(n+1)x^n \]两边同时复合 \(x+a\)，可得
\[F(x+a)-F'(x+a)\cdot(1-a-x)=(n+1){(x+a)}^n \]考虑将 \(F(x+a)\) 替换成 \(\mathscr{F}(x+a)\) 会产生什么影响。
\[\mathscr{F}(x+a)-\mathscr{F}'(x+a)\cdot(1-a-x)=[(n+1){(x+a)}^n \bmod{x^{k+1}}]+[x^k]F'(x+a)\cdot(1-a-x) \] 标签：right,ae,mathscr,Sum,笔记,circ,Binomial,frac,left From： https://www.cnblogs.com/FidoPuppy/p/18236293