感性理解 【EI 载谭 Binomial Sum】

这篇文章主要是给自己看的，所以说的非常感性！！！

先简要叙述一下 Binomial Sum 的过程：

有一个函数 \(T(x)\)（在这篇文章中，默认 \(T(x)=e^x\)），满足对于每个 \(k\)，都可以快速求出：（其中 \(k\) 较小，\(n\) 较大）

\[\sum_{i=0}^n a_i[x^i]T(x)^k \]

通过 Binomial Sum，我们可以求出

\[\sum_{i=0}^n a_iF(e^x) \]

（我们在这篇文章中，只讨论求 \([x^k]F(e^x)\) 的方法）

\[F\circ e^x=F\circ (1+x)\circ (e^x-1)=F(1+x)\circ(e^x-1) \]

遗憾的是，我们无法快速求得其值，即：（令 \(G=F(x+1)\)）

\[\sum_{i=0}^n g_i(e^x-1)^i \]

但是由于 \(e^x-1\) 没有常数项，我们这个求和式可以在 \(k\) 停止，即我们可以将 \(G\) 截断成多项式 \(P=G\bmod x^{k+1}\)。

我们尝试将其向一个已经解决了的问题 \(\sum_{i=0}^n q_ie^{ix}\) 进行转化。

我们发现，\(P\) 与 \(Q\) 之间满足：\(P\circ (x-1)\circ e^x=Q\circ e^x\)，即 \(Q=P\circ (x-1)\)。

那么我们只需在线性内求出 \((((F\circ(x+1))\bmod x^{k+1})\circ(x-1)\) 的各项系数即可 \(O(n)\) 解决该问题。

下面以 CF392C 为例演示其详细过程。

\[\sum_{i=0}^n fib_ii^k=\sum_{i=0}^nfib_i[\frac{x^k}{k!}]e^{ix}=[\frac{x^k}{k!}](Fib\bmod x^{n+1})(e^x) \]

令 \(F(x)=Fib(x)\bmod x^{n+1}\)，在整式递推的角度，模 \(x^{n+1}\) 对 \(\leqslant n\) 的 \(f_i\) 转移没有影响，同样地，其对 \(>n+2\) 的整式递推也不会有影响（因为全是 \(0\) 了），我们只需手动修正 \(n+1,n+2\) 这两个次数对应的项即可。

\[F-xF-x^2F=1-(fib_{n-1}+fib_n)x^{n+1}-fib_n x^{n+2}\\F=\frac{1-fib_{n+1}x^{n+1}-fib_nx^{n+2}}{1-x-x^2} \]

然后开始 Binomial Sum 的第一步：（令 \(G(x)=1-fib_{n+1}x^{n+1}-fib_nx^{n+2}\)）

我们首先复合上 \(x+1\)：

\[F(x+1)=\frac{G(x+1)}{1-(x+1)-(x+1)^2}=-(G(x+1)+3xF(x+1)+x^2F(x+1)) \]

若我们得知了 \(G(x+1)\) 的各项系数，就可以直接提取系数递推了。

妈的，鸽了。

Prean-把EI科技 【载谈 Binomial Sum】 用人话说出来

zxy-【翻译】载谭Binomial Sum

alpha1022-P5430 [SNOI2017]礼物 加强版

alpha1022-载谭 Binomial Sum 小练习

EI-载谭 Binomial Sum：多项式复合、插值与泰勒展开

EI-「实验性讲稿」载谭 Binomial Sums 详解