Binomial Sum
如果我们有一个微分有限函数 \(F(z)\)，还有另外一个生成函数 \(G(z)\)，一个数列 \(a\)，如果我们能对 \(k\in[0,n]\) 的每一个 \(k\) 快速求出 \(G^k(z)\) 的前 \(n\) 项系数带权和，即
\[b_k=\sum_{i=0}^na_i[z^i]G^k(z) \]那么我们可以在 \(\Theta(n)\) 的时间复杂度内计算出来
\[\sum_{i=0}^na_i[z^i]F(G(z)) \]设 \(c=[z^0]G(z)\)，令 \(F\) 在 \(c\) 处展开，代入 \(G(z)\)，得到：
\[F(G(z))=\sum_{k=0}F^{(k)}(c)\frac {(G(z)-c)^k}{k!} \]由于 \(z|G(z)-c\)，所以对于我们需要计算的 \(\sum_{i=0}^na_i[z^i]F(G(z))\) ，我们只需要展开到 \(n\) 次项即可。
由于 \(F(z)\) 是微分有限的，所以我们知道存在微分方程：
\[\sum_{j=0}^mp_j(z)F^{(j)}(z)=0\\ \sum_{j=0}^mp_j(z+c)F^{(j)}(z+c)=0\\ \]我们考虑我们只需要 \(F(z+c)\) 的前 \(n\) 项，所以我们考虑截取，令 \(H(z+c)=F(z+c)\bmod z^{n+1}\)，则我们知道存在微分方程使得：
\[\sum_{j=0}^mp_j(z+c)H^{(j)}(z+c)=D(z)\\ \sum_{j=0}^mp_j(z)H^{(j)}(z)=D(z-c)\\ \]\(D(z)\) 的原因是因为 \(F\) 的 \(z^{n+1}\) 项本来求导后也会对 \(z^n\) 项贡献，但是由于我们的截取导致会少掉这一部分的贡献，所以需要扰动。
此时 \(H\) 只有 \(n\) 项，我们可以考虑递推。
CF932E Team work
给定 \(n,k\)，求
\[\sum_{i=0}^n\binom n ii^m \]\(1\le n\le 10^9,1\le m\le 5000\)。
Bonus：\(1\le m\le 10^7\)。
考虑
\[\begin{aligned} Ans&=[\frac {z^m}{m!}]\sum_{i=0}^n\binom n ie^{iz}\\ &=m^n \end{aligned} \]然后我们设 \(F(z)=(z+1)^n,G(z)=e^z\)，然后我们令 \(a_{m}=m!\)，其他的 \(a_i=0\)，则 \(b_i=m![{z^m}]e^{iz}=i^m\)，然后我们考虑
\[\begin{aligned} (z+1)F'(z)-nF(z)&=0\\ (z+2)F'(z+1)-nF(z+1)&=0 \end{aligned} \]令 \(H(z+1)=F(z+1)\bmod z^{m+1}\)，则我们手玩后得到：
\[\begin{aligned} (z+2)H'(z+1)-nH(z+1)&=-2z^m[z^m]F'(z+1)\\ (z+2)H'(z+1)-nH(z+1)&=-2nz^m[z^m](z+2)^{n-1}\\ (z+2)H'(z+1)-nH(z+1)&=-2nz^m\binom {n-1}m2^{n-m-1}\\ (z+2)H'(z+1)-nH(z+1)&=-n2^{n-m}\binom {n-1}mz^m\\ (z+1)H'(z)-nH(z)&=-n2^{n-m}\binom {n-1}m\sum_{j=0}^m\binom m j(-1)^{m-j}z^j\\ (i+1)h_{i+1}+(i-n)h_i&=-n2^{n-m}\binom {n-1}m\binom m i(-1)^{m-i}\\ h_i&=\frac1 {n-i}((i+1)h_{i+1}+n2^{n-m}\binom {n-1}m\binom m i(-1)^{m-i}) \end{aligned} \]然后我们可以提取系数递推即可。
\[Ans=\sum_{i=0}^mb_i[z^i]H(z)=\sum_{i=0}^mi^mh_i \]P6667 [清华集训2016] 如何优雅地求和
有一个多项式函数 \(f(x)\)，最高次幂为 \(x^m\)，定义变换 \(Q\)：
\[Q(f,n,x)=\sum_{k=0}^{n}f(k)\binom nkt^k(1−t)^{n−k} \]现在给定函数 \(f\) 和 \(n,t\)，求 \(Q(f,n,x)\bmod998244353\)。
出于某种原因，函数 \(f\) 由点值形式给出，即给定 \(a_0,a_1,⋯,a_m\) 共 \(m+1\) 个数，\(f(x)=a_x\)。可以证明该函数唯一。
\(1\le m\le 2\times 10^4,1\le n\le 10^9,0\le a_i,x< 998244353\)。
我们设 \(f(k)=\sum_{i=0}^mf_ik^i=\sum_{i=0}^mf_ii![z^i]e^{kz}\)，然后我们考虑这个问题。
\[\begin{aligned} Ans&=\sum_{i=0}^m\sum_{k=0}^nf_ik^i\binom n kt^k(1-t)^{n-k}\\ &=\sum_{i=0}^mf_ii![z^i]\sum_{k=0}^ne^{kz}\binom n kt^k(1-t)^{n-k}\\ &=\sum_{i=0}^mf_ii^n \end{aligned} \]然后我们设 \(F(z)=(tz+1-t)^n,G(z)=e^z\)，则 \(a_i=f_ii!,b_i=f_i\),\(c=[z^0]G(z)\)。
然后我们考虑
\[(tz+1-t)F'(z)-ntF(z)=0\\ (tz+1)F'(z+1)-ntF(z+1)=0 \]令 \(H(z+1)=F(z+1)\bmod z^{m+1}\)，得到：
\[\begin{aligned} (tz+1)H'(z+1)-tnH(z+1)&=-z^m[z^m]F'(z+1)\\ (tz+1)H'(z+1)-tnH(z+1)&=-ntz^m[z^m](tz+1)^{n-1}\\ (tz+1)H'(z+1)-tnH(z+1)&=-ntz^m\binom {n-1}mt^m\\ (tz+1-t)H'(z)-tnH(z)&=-nt^{m+1}\binom {n-1}m(z-1)^m\\ (tz+1-t)H'(z)-tnH(z)&=-nt^{m+1}\binom {n-1}m\sum_{i=0}^m\binom m i(-1)^{m-i}z^i\\ (1-t)(i+1)h_{i+1}+ith_i-tnh_i&=-nt^{m+1}\binom {n-1}m \binom m i(-1)^{m-i}\\ (n-i)th_i&=(i+1-ti-t)h_{i+1}+nt^{m+1}\binom {n-1}m\binom m i(-1)^{m-i}\\ h_i&=\frac 1 {(n-i)t}((i+1-ti-t)h_{i+1}+nt^{m+1}\binom {n-1}m\binom m i(-1)^{m-i}) \end{aligned} \]然后递推即可。
P5907 数列求和加强版 / SPOJ MOON4
给定 \(n,q,k\)，求
\[\sum_{i=1}^ni^kq^i \]\(1\le k\le 10^7,1\le n,a<998244353\)
考虑 \([\frac {z^k}{k!}](qe^{z})^i=q^ii^k\)，所以：
\[Ans=[\frac {z^k}{k!}]\sum_{i=0}^n(qe^z)^i=k![z^k]\frac {1-(qe^z)^{n+1}}{1-qe^z} \]设 \(F(z)=\frac {1-z^{n+1}}{1-z},G(z)=qe^z\)，那么 \(a_k=k!\)，\(a_i=0\)，然后 \(b_i=k![z^k]q^ie^{iz}=q^ik^i\) ，\(c=[z^0]G(z)=q\)。
那么我们知道：
\[\begin{aligned} (1-z)F'(z)-F(z)&=-(n+1)z^n \end{aligned} \]所以
\[\begin{aligned} (1-z-q)F'(z+q)-F(z+q)&=-(n+1)(z+q)^n\\ (1-z-q)H'(z+q)-H(z+q)&=-(n+1)(z+q)^n-(1-q) z^k[z^{k}]F'(z+q)\\ \end{aligned} \]鸽了！！！！
标签：le,tz,Sum,笔记,Binomial,end,binom,aligned,sum From： https://www.cnblogs.com/Nityacke/p/18165288