前情提要：模拟赛就要出三个大模拟，字面意思上的模拟赛。所以发动了魔法卡献祭了模拟赛来写这个东西。
我刚改邪归正准备好好敲暴力你就给我来这个？建议出题人自己写。
感觉写博逐渐倾向于告诉自己“我学了这个东西但是以后可能会忘所以记下来”这种心态。算了反正模拟赛狗都不打。
一开始看 EI 的原文，看的一知半解。然后看 Prean 老师的洛谷日报，整不会了。然后找了几篇题解，似乎大概知道了这是个什么过程。但是并不明白这个名字是什么意思。
感觉直接上例题来解释这个过程是如何运行的会更好理解一点。
以下所有题默认 \(k\le n\)。
CF932E Team Work
题意：求
\[\sum_{i=1}^n\binom nii^k \]首先我们会 \(O(k\log k)\)，直接把后边的 \(i^k\) 爆拆斯特林数随便推一下就成。不过这不重要。
我们的技术首先把这个式子变成某个生成函数的 \(k\) 项的形式。
\[\begin{aligned} &\sum_{i=1}^n\binom nii^k\\ =&\sum_{i=0}^n\binom ni[x^k]e^{ix}\\ =&[x^k](e^x+1)^n \end{aligned} \]设 \(F(x)=(x+1)^n\)，则答案就是 \([x^k]F(e^x)\)。Binomial sum 的方法通过去除函数的常数项达到只需要求得 \(x^{k+1}\) 以内的项即可得到答案的效果。\(e^x\) 的常数项为 \(1\)，则我们设
\[\mathcal F(x+1)=F(x+1)\bmod x^{k+1} \]则我们断言答案是 \([x^k]\mathcal F(x)\)。证明考虑泰勒展开的 \(k\) 次项以后都是不需要的，详见 EI 原文。
那么我们此时列出 \(F(x)\) 满足的微分方程：
\[(x+1)F'(x)-nF(x)=0 \]那么将 \(x\) 替换为 \(x+1\)，显然有
\[(x+1+1)F'(x+1)-nF(x+1)=0 \]此时我们将 \(F(x+1)\) 替换为 \(\mathcal F(x+1)\)。然而此时不能随意替换。注意到原本的 \((x+1+1)F'(x+1)\) 由于求导，在 \([x^k]\) 处有 \(x^k,x^{k+1}\) 两项的贡献。而在 \(x^{k+1}\) 处截取之后没有了 \(x^{k+1}\) 项的贡献，所以我们需要把截取后的 \(x^k\) 项手算出来。根据 \(F(x)=(x+1)^n\) 把项拆出来，简单手算一下可以得到：
\[(x+1+1)\mathcal F'(x+1)-n\mathcal F(x+1)=(k-n)x^k[x^k]F(x+1) \]注意等式右边是 \(F\)。然后带入 \(x\leftarrow x-1\)：
\[(x+1)\mathcal F'(x)-n\mathcal F(x)=(k-n)(x-1)^k[x^k]F(x+1) \]右边是个系数所以仍然是 \(F(x+1)\)。
算一下右边：
\[\begin{aligned} &(k-n)(x-1)^k[x^k]F(x+1)\\ =&(k-n)\binom nk2^{n-k}\sum_{i=0}^k\binom kix^i(-1)^{k-i} \end{aligned} \]于是可以递推。具体列递推式：
\[(i+1)f_{i+1}+if_i-nf_i=(k-n)\binom nk2^{n-k}\binom ki(-1)^{k-i} \]一个比较笨的方法是把 \(f_0\) 通过某些方式（按照定义）算出来然后从下往上推。
一个比较高明的方式是发现 \(f_{k+1}=0\)，然后可以直接倒着推回来。
得到了 \(\mathcal F(x)\) 的各项系数后，即可得到答案
\[\begin{aligned} &[x^k]\mathcal F(e^x)\\ =&[x^k]\sum_{i=0}^kf_ie^{ix}\\ =&\sum_{i=0}^kf_ii^k \end{aligned} \]可以 \(O(k)\) 算出。大致就是这样的过程。我们见到的应用多为 \(F(e^x)\) 的形式，但里边的函数其实可以换成别的，详见 EI 原文。
P5907 数列求和加强版 / SPOJ MOON4
另一道例题。首先经过简单转化，答案为
\[[x^k]\frac{1-(ae^x)^{n+1}}{1-ae^x} \]于是设 \(F(x)=\dfrac{1-x^{n+1}}{1-x}\)。求导表示自己得到 ODE（设 \(G(x)=1-x^{n+1}\)）
\[(1-x)F'(x)=G'(x)+F(x) \]于是
\[(1-x-a)F'(x+1)=G'(x+a)+F(x+a) \]仍设 \(\mathcal F(x+a)=F(x+a)\bmod x^{k+1},\mathcal G(x+a)=G(x+a)\bmod x^{k+1}\)，有
\[(1-x-a)\mathcal F'(x+a)-\mathcal F(x+a)=-(n+1)\sum_{i=0}^k\binom nix^ia^{n-i}-(k+1)x^k[x^k]F(x+a) \]\[(1-x)\mathcal F'(x)-\mathcal F(x)=\mathcal G'(x)-(k+1)(x-a)^k[x^k]F(x+a) \]算下 \(\mathcal G'(x)\)（这里 \(n\leftarrow n+1\)）：
\[\begin{aligned} \mathcal G(x+a)=&\sum_{i=0}^k\binom nix^ia^{n-i}\\ \mathcal G(x)=&\sum_{i=0}^k\binom nia^{n-i}(x-a)^i\\ =&\sum_{i=0}^k\binom nia^{n-i}\sum_{j=0}^i\binom ijx^j(-a)^{i-j}\\ =&\sum_{j=0}^k\binom njx^ja^{n-j}\sum_{i=j}^k\binom{n-j}{i-j}(-1)^{i-j}\\ =&\sum_{j=0}^k\binom njx^ja^{n-j}\sum_{i=0}^{k-j}\binom{n-j}{i}(-1)^i\\ =&\sum_{j=0}^k\binom njx^ja^{n-j}[x^{k-j}]\frac{(1-x)^{n-j}}{1-x}\\ =&\sum_{j=0}^k\binom njx^ja^{n-j}\binom{n-j-1}{k-j}\\ \mathcal G'(x)=&\sum_{i=1}^k\binom nix^{i-1}a^{n-i}\binom{n-i-1}{k-i}\\ \end{aligned} \]另一边：
\[\begin{aligned} &(k+1)(x-a)^k[x^k]F(x+a)\\ =&(k+1)\sum_{i=0}^k\binom kix^i(-a)^{k-i}[x^k]\sum_{j=0}^n(x+a)^j\\ =&(k+1)\sum_{i=0}^k\binom kix^i(-a)^{k-i}h_k \end{aligned} \]考虑计算 \(h_k=\sum_{i=k}^n\dbinom ika^{i-k}\)：
首先特判 \(a=1\)，上指标求和得到是 \(\dbinom{n+1}{k+1}\)。
\[\begin{aligned} h_k=&\sum_{i=k}^n\binom ika^{i-k}\\ =&\sum_{i=k}^n\left(\binom{i-1}{k-1}+\binom{i-1}k\right)a^{i-k}\\ =&\sum_{i=k-1}^{n-1}\binom i{k-1}a^{i-(k-1)}+a\sum_{i=k}^{n-1}a^{i-k}\binom ik\\ =&h_{k-1}-a^{n-k+1}\binom n{k-1}+a\left(h_k-q^{n-k}\binom nk\right) \end{aligned} \]可以递推。于是可以递推得到 \(\mathcal F(x)\)，答案即为 \(\sum_{i=0}^kf_ia^ii^k\)。
实际上有时候并没有有限微积分的方法简洁，但是它的重要意义是提出了一个通用的方法。
标签：begin,end,sum,binomial,mathcal,binom,aligned From： https://www.cnblogs.com/gtm1514/p/17364998.html