Binomial Sum 学习笔记

这是EI写的一个神秘科技。我只能把它最简单的东西讲述出来。
用于\(O(k+\log n)\)复杂度解决一类求和问题。
使用条件：\(f(x)\)微分有限，话句话说，存在\(f\)的微分方程。
如果我容易知道\(\displaystyle\sum_{i=0}^{n}a_i[x^i]G(x)^k,k\in[0,]\)，那么我就可以\(O(n)\)求\(\displaystyle\sum_{i=0}^n a_i[x^i]F(G(x))\)。
考虑对\(F\)泰勒展开。\(\displaystyle\sum_{k\ge 0}F^{(k)}(G(0))\dfrac{(G(x)-G(0))^k}{k!}\)。
这有什么优势呢？对于\(x\)，可以发现\(k\)大于\(n\)的项是对答案没有贡献的，因为没有常数项。
设\(F(x)\)满足微分方程\(\displaystyle\sum_{i=0}^m p_i(x)F^{(i)}(x)=0\)。
易知\(\displaystyle\sum_{i=0}^m p_i(x+G(0))F^{(i)}(x+G(0))=0\)
现在我可以截取他的前\(n\)项系数变为\(\mathcal{F}\)。
这里可以认为是\(\mathcal{F}=F\mod (x-c)^n\)
\(\displaystyle\sum_{i=0}^m p_i(x+G(0))\mathcal{F}^{(i)}(x+G(0))=0\)
注意到跨过\(x^n\)的贡献突然出现，右边加上这个就可以\(O(nm)\)递推。
然后多项式带入原式，就可以\(O(n)\)求答案。
一般认为\(m\)是常数。

CF932E 加强版

给定 \(n,k\)，求：$\displaystyle\sum_{i=1}^n\binom{n}{i}\times i^k,1 \leq k \leq 10^7,1 \leq n \leq 10^9 $。
不妨从\(0\)开始。
发现\(i^k=[\dfrac{x^k}{k!}]e^{xi}\)。
于是原式等于\(\displaystyle[\frac{x^k}{k!}]\sum_{i=0}^n\binom{n}{i}e^{ix}\)
等于\([\dfrac{x^k}{k!}](e^x+1)^n\)。
至此可以\(O(k\log k\log n)\)多项式快速幂，但是这不令人满足。
魔法，启动！
这里设\(F(x)=(x+1)^n,\mathcal{F}(x+1)=F(x+1)\mod x^{k+1}\)。
注意：\(F\)可以随意变换，但\(\mathcal{F}\)由于其特殊定义不能随便乱搞。
\((x+1)F'(x)-nF(x)=0\)
\((x+2)F'(x+1)-nF(x+1)=0\)
手推发现(这里\(x^k\)接收了从\(x^{k+1}\)来的不合法贡献)\((x+2)\mathcal{F}'(x+1)-n\mathcal{F}(x+1)=(k-n)x^k[x^k]F(x+1)\)。
发现右边可以乱搞，于是令\(x-1\to x\)。
\((x+1)\mathcal{F}'(x)-n\mathcal{F}(x)=(k-n)(x-1)^k [x^k]F(x+1)\)
于是可以得到\([x^i]\mathcal{F}\)的递推式。
具体来说，展开右边，令两边系数相等，得到：
\((i+1)f_{i+1}+if_i-nf_i=(k-n)\binom{n}{k}2^{n-k}\binom{k}{i}(-1)^{k-i}\)。
固然可以算\(f_0\)，但更好的方法是发现\(f_{k+1}=0\)。
最后的答案，就是\([\dfrac{x^k}{k!}]\mathcal{F}(e^x)=[\dfrac{x^k}{k!}]\displaystyle{\sum_{i=0}^k e^{ix}[x^i]\mathcal{F}(x)}\)。
\([\dfrac{x^k}{k!}]\mathcal{F}(e^x)=[\dfrac{x^k}{k!}]\displaystyle{\sum_{i=0}^k e^{ix}[x^i]\mathcal{F}(x)}=\displaystyle{\sum_{i=0}^k i^k[x^i]\mathcal{F}(x)}\)\
做完了。
注意，这里不可以把\(\mathcal{F}\)任何方法展开。
本题中，\(G(x)=e^x,F(x)=(x+1)^n\)。
给我的感觉是这个玩意的难点在于构造\(F,G\dots\)，，，
可能是我太菜了
看了半个小时没看懂，原来是展开掉了一个组合数，，，

P6667 如何优雅的求和

有一个多项式函数 \(f(x)\)，最高次幂为 \(x^m\)，定义变换 \(Q\)：

现在给定函数 \(f\) 和 \(n,x\)，求 \(Q(f,n,x)\bmod998244353\)。
出于某种原因，函数 \(f\) 由点值形式给出，即给定 \(a_0,a_1,?,a_m\) 共 \(m+1\) 个数，\(f(x)=a_x\)。可以证明该函数唯一。
构造\(G(x)=e^x,F(x)=(ax+1-a)^n\)。(避免混淆，这里把\(x\)写作\(a\)，但是注意\(a_i\)和\(a\)的区别)
接下来说明这个东西的正确性：
\([x^j]F(G(x))=(ae^x+1-a)^n =\displaystyle\sum_{i=0}^n \binom{n}{i}a^i(1-a)^{n-i}[x^j]e^{ix}\)。
而\([x^j]e^{ix}=\dfrac{i^j}{j!}\)，所以原式\(=\displaystyle\sum_{i=0}^n \binom{n}{i}a^i(1-a)^{n-i}\dfrac{i^j}{j!}\)。
令\([x^j]f(x)=\frac{a_j}{j!}\)，那么\(\displaystyle \sum_{j=0}^ma_j[x^j]G(x)^k=f(k)\)。
式子\(\displaystyle\sum_{j=0}^ma_j[x^j]\sum_{i=0}^n \binom{n}{i}a^i(1-a)^{n-i}\dfrac{i^j}{j!}\)
\(=Q(f,n,x)\)。
然后按照 Binomial Sum 的现成方法来就可以了。
这里容易发现 \(F\) 满足的一个微分方程：
\((ax+1-a)F'(x)-anF(x)=0\)。
\(G(0)=1\),所以设 \(\mathcal{F}(x)=F(x)\bmod(x-1)^{m+1}\)，或\(\mathcal{F}(x+1)=F(x+1)\bmod x^{m+1}=(ax+1)^n \bmod x^{m+1}\)。
微分方程变换为 \((ax+1)F'(x+1)-anF(x+1)=0\)，以预备换为关于 \(\mathcal{F}\) 的方程。
考察 \((ax+1)\mathcal{F}'(x+1)-an\mathcal{F}(x+1)\)，其不合法的项从哪里来？
显然只有 \(\mathcal{F}'\) 从其原函数的 \(m+1\) 次跨向 \(m\) 次中来。
所以 \((ax+1)\mathcal{F}'(x+1)\)，具体地说是后面那个 \(1\mathcal{F}'(x+1)\) 获得了贡献。但是实际上不存在。所以要在右边减去。
所以右边等于 \(-x^m[x^m]F'(x+1)=-na^{m+1}\binom{n-1}{m}x^m\)。
于是右边是一个可以变化、展开的项，令 \(x-1\to x\)。
然后得到 \((ax+1-a)\mathcal{F}'(x)-an\mathcal{F}(x)=-na^{m+1}\binom{n-1}{m}(x-1)^{m}\)。
于是提取系数，具体来说：
设 \([x^i]\mathcal{F}(x)=f_i\)，\([x^i]\) 左式 \(=(1-a)(i+1)f_{i+1}+aif_i-anf_i\)。
同时 \([x^i]\) 右式 \(=-na^{m+1}\binom{n-1}{m}\binom{m}{i}(-1)^{m-i}\)。
由于两边多项式相等，系数也相等，左式等于右式，得出 \(f_i\) 递推式。
此时计算得到 \(f_0\) 的值是不明智的。注意到 \(f_{m+1}=0\)，倒着推即可。注意特判 \(n\le m\)。
精细实现（预处理连续逆元）可以做到 \(O(m)\)，不精细实现则是小常数 \(O(m\log m)\)，吊打 NTT。