【n 次翻译】载谭 Binomial Sum

没有想到机房大佬再一个月前就卷过这个科技：[Youwike 大佬的博客](https://www.cnblogs.com/i209M/p/16335551.html)。

[载谭 Binomial Sum：多项式复合、插值与泰勒展开](https://www.luogu.com.cn/blog/EntropyIncreaser/zai-tan-binomial-sum-duo-xiang-shi-fu-ge-cha-zhi-yu-tai-lei-zhan-kai)

[把EI科技 【载谈 Binomial Sum】 用人话说出来](https://www.luogu.com.cn/blog/lmpp/post-zai-tan-binomial-sum)

[两类递推数列](https://blog.csdn.net/qq_35950004/article/details/106909200)

[整式递推数列](https://blog.csdn.net/qq_35950004/article/details/103952118)

## Part.1 定义

微分有限：对于多项式 $A$，满足:
>$$
\sum_{i=0}^{k}P_i(x)A^{(i)}(x)=C(x)
>$$

>其中 $P_i(x)$ 为有限多项式，则称 $A$ 为微分有限的（**D-Finite**）。

整式递推：对于多项式 $A$，满足：

>$$
\forall p \ge k,Q_{k}!= 0,\sum_{i=0}^{k}Q_i(p)[x^{p-i}]A(x) =C(x)
>$$

>其中 $Q$ 为有限的多项式，则称 $Q$ 为 $A$ 的**整式递推式**。

形式代数幂级数：若 $A$ 是方程 $\sum_{i=0}^{k}R_i(x)A(x)=C(x)$ 的一组解，则称 $A$ 为**形式代数幂级数**。

**定理1**：$A$ 为微分有限当且仅当 $A$ 存在整式递推式。

> 证明：他们看起来就差一些求导带来的常数项，就假装他可以吧。

**定理2**：若 $A$ 为形式代数幂级数，则 $A$ 微分有限。

> 证明：这看着就很对，就不（会）证了。。。

常见的微分有限函数：

>有限函数，还有普通的生成函数，其他不知道

他能干什么：

> 可以通过微分方程用来计算递推式，从 $\sum_{i=0}^{k}P_i(x)A^{(i)}(x)=C(x)$ 来导出 $\forall p \ge k,Q_{k}!= 0,\sum_{i=0}^{k}Q_i(p)[x^{p-i}]A(x) =C(x)$，那么 $Q_i(p)$ 就是我们要求的递推式。在实战中基本上满足 $Q_i(p)$ 和 $P_i(x)$ 都是常数。

## Part.2 Binomial Sum 理论指导

（式子与 EI 稍微有点出入）。

如果我们能够快速知道

$$
\forall k\in[0,n],(G(x)-G(0))^{k}
$$

且 $f$ 为微分有限（设他的微分方程为 $\sum_{i=0}^{m}p_if^{(i)}(x)=0$），那么我们通常可以 $O((n+m)m)$ （$m$ 通常为 $O(1)$）算出

$$
\sum_{j=0}^{n}a_j[x^j]f(G(x))
$$

的值。~~感觉不是很平凡~~。

---------------

首先 $\forall k\in[0,n],(G(x)-G(0))^{k}$ 在干什么？注意到 $G(x)-G(0)$ 没有常数项，即 $x|(G(x)-G(0))$，如果我们要求 $[x^{0}]$ 到 $[x^n]$，我们就不需要管 $(G(x)-G(0))^{k>n}$。因为 $G$ 通常不是很规则（如 $e^{x}+1$），因此我们通常借此简化 $G$ 的求值运算。

那么对于 $f(G(x))$，一个朴素的想法就是让他在 $G(0)$ 处泰勒展开：

$$
f(G(x))=\sum_{0\le i\le n}f^{(i)}(G(0))\frac{(G(x)-G(0))^i}{i!}
$$

但是 $f^{(i)}(G(0))$ 通常不是那么好求，难点在于你需要先求导再带入。那么我们考虑换种思路，通过 $f$ 的变换在定义域内把 $G(0)$ 给消掉。

一个的想法就是求出 $f(x+G(0))=\sum_{i=0}^{n}p_{1_i}x^{i}$

因此我们考虑 $f$ 的微分方程（应该可以化成整式递推式，但我没有贺到过，就不写了）：

$$
\sum_{i=0}^{m}p_i(x)f^{(i)}(x)=0
$$

（我也不知道为什么要另起一个 $f$ 进行计算）我们截取 $f(x+G(0))=F(x+G(0)) \pmod {x^{n+1}}$，考察这个新的微分方程长什么样：与原来不同的唯一区别就是在微分方程中大于等于 $x^{n+1}$ 的项求导之后产生的影响，即：

$$
\sum_{i=0}^{m}p_i(x+G(0))f^{(i)}(x+G(0)) =0 \pmod {x^{n+1}}
$$
$$
\sum_{i=0}^{m}p_i(x+G(0))(F^{(i)}(x+G(0))+ \sum_{j=n+1-i}^{n}x^j([x^j]f^{(i)}(x+G(0))))=0 \pmod {x^{n+1}}
$$

暴力算出 $m^2$ 个 $f$ 的贡献，于是我们就能推导出 $F(x+G(0))$ 的整数递推式，从而快速求出 $[x^0]$ 到 $[x^{n}]$。那么原问题变成：

$$
\sum_{j=0}^{n}a_j[x^j]F(G(0))=\sum_{i=0}^{n}a_j[x^j]f(G(0))
$$
$$
=\sum_{j=0}^{n}a_j [x^j](\sum_{i=0}^{n}p'_ix^i(G(x)-G(0))^i)
$$

然后通过一些骚操作把 $(G(x)-G(0))^i$ 搞掉就行。

实战：GDFZOJ 20230705 模拟赛 T3，这是 lh 对后辈贴心的问候（暂时没写）。

正在渲染内容...

【n 次 翻译】载谭 Binomial Sum

【n 次翻译】载谭 Binomial Sum