# Grox的序列六：Newton 二项式基底

**Codex（GPT-6）：用有限差分把多项式转换到二项式基底，使特解方程变为相邻系数递推。** 有限差分与 Newton 展开是通用方法；本题应用与实现见[计算程序](alternative-newton.cpp)。[幂基底系数矩阵方案](solution.zh.md)仍作标程，两者并列。

## 移位后的基底

令 $T(n)=\sum_{i=0}^k a_i n^i$ .先在 $1,2,\ldots,k+1$ 求值，然后逐层作相邻差，得到

$$t_j=\Delta^jT(1),\qquad T(n)=\sum_{j=0}^k t_j\binom{n-1}{j}$$

这里 $\Delta T(x)=T(x+1)-T(x)$ .二项式多项式满足 $\Delta\binom{x}{j}=\binom{x}{j-1}$ ，所以逐次取差准确提取 Newton 系数；次数不超过 $k$ 的多项式由这 $k+1$ 个值唯一确定。

用另一个移位位置表示特解：

$$g(n)=\sum_j c_j\binom nj$$

由 Pascal 恒等式，

$$g(n)-\beta g(n-1)=\sum_j\big((1-\beta)c_j+c_{j+1}\big)\binom{n-1}{j}$$

原来的完整三角系统变为相邻两项的关系。

## 两种 beta

当 $\beta\ne1$ 时，取 $c_{k+1}=0$ ，从高到低求

$$c_j=\frac{t_j-c_{j+1}}{1-\beta}\qquad(j=k,k-1,\ldots,0)$$

当 $\beta=1$ 时，直接取 $c_0=0$ 与 $c_{j+1}=t_j$ ，得到次数不超过 $k+1$ 的离散原函数。不需要为单项式逐个存储基函数。

两个分支均使用

$$f(n)=g(n)+(\alpha-c_0)\beta^n$$

查询时从 $\binom n0=1$ 开始，用

$$\binom n{j+1}=\binom nj\frac{n-j}{j+1}$$

线性求值。分母最多为 $k+2<P$ ，逆元总是存在；即使 $n<j$ 后系数为零，也不对零做除法。零次幂采用 $\beta^0=1$ ，保证 $\beta=0,n=0$ 的初值。

## 正确性与复杂度

有限差分给出准确的 $T$ 展开，相邻系数关系保证特解方程成立。指数项满足齐次递推，且公式在零下标等于 $\alpha$ ，由初值递推的唯一性得到所有项。替换重新计算整组 Newton 系数。

沿用主题解的 $Q_0,Q_1,N_{\max}$ .预处理整数逆元及一个模逆元需 $O(k+1+\log P)$ 时间；每次初始读入或替换需 $O((k+1)^2)$ 时间；查询需 $O(k+1+\log(n+1))$ 时间。总时间

$$O(k+1+\log P+(Q_1+1)(k+1)^2+Q_0(k+1+\log(N_{\max}+1)))$$

空间为 $O(k+1)$ .相较幂基底方案，省去立方级基函数预处理与平方级系数矩阵；替换与查询的渐进阶相同，但二项式查询每项包含更多模乘。两者的实际性能取决于操作组合，不因较少预处理就宣称每种输入都更快。

## 同输入测量

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.045359 秒，补充方案为 0.081370 秒；峰值工作集分别为 5.84 与 5.33 MiB，包含进程与运行库开销。
补充程序在全部已测正式输入上均低于 0.5 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。