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

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

移位后的基底¶

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