# Grox的序列六题解

**出题人解法：预处理多项式特解的系数矩阵，以多项式与指数项表示递推。** Codex（GPT-6）将 $\beta=1$ 的特解显式写成差分求和分支，保留负数与零次幂的处理，并在替换参数时合成系数，使查询从逐个基函数求值改为对一个多项式求值。

## 多项式特解

所有计算在模 $P=1000000007$ 下进行。令

$$T(n)=\sum_{i=0}^k a_i n^i$$

当 $\beta\ne1$ 时，寻找次数不超过 $k$ 的多项式 $g(n)$ ，使

$$g(n)-\beta g(n-1)=T(n)$$

若 $g(n)=\sum_{j=0}^k c_j n^j$ ，比较 $n^d$ 的系数得到

$$(1-\beta)c_d-\beta\sum_{j=d+1}^k\binom jd(-1)^{j-d}c_j=a_d$$

这是从高次数到低次数求解的三角系统，且 $1-\beta$ 可逆。先为每个基函数 $T(n)=n^i$ 求出一组系数，记对应多项式为 $g_i(n)$ .

对任意参数，以线性组合 $g(n)=\sum_i a_i g_i(n)$ 得到特解，进而

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

后一项满足齐次递推，零下标项等于 $\alpha$ ，所以公式满足完整初值与递推。模幂在这里遵循 $\beta^0=1$ ，包括 $\beta=0$ ，保证查询零下标得到初值；$n>0,\beta=0$ 则指数项为零。

## 当 beta 等于一

此时 $1-\beta$ 不可逆，改用次数不超过 $k+1$ 且 $g(0)=0$ 的离散原函数：

$$g(n)-g(n-1)=T(n)$$

系数系统为

$$\sum_{j=d+1}^{k+1}(-1)^{j-d+1}\binom jd c_j=a_d\qquad(0\le d\le k)$$

从 $d=k$ 向下求解，每行 $c_{d+1}$ 的系数为 $d+1$ .这些整数小于 $P$ ，均可逆；令 $c_0=0$ 唯一确定多项式。仍然逐个预处理单项式基函数。此时答案为 $f(n)=\alpha+g(n)$ ，与上面的统一表达式一致。

## 查询与替换的取舍

出题人预处理每个基函数后，在每次查询分别求值，再按当前 $a_i$ 加权。系数比较与消元正确给出这些基函数；一次查询的多项式求值为 $O((k+1)^2)$ ，再加模幂时间。参数替换只需保存输入，代价为 $O(k+1)$ .

标程保留这个系数预处理方法，在每次初始读入或替换时先合成 $g$ 的系数和 $\alpha-g(0)$ .替换需 $O((k+1)^2)$ ；查询用 Horner 法求值，需 $O(k+1+\log(n+1))$ .当一组参数后有多次查询时，这避免重复加权；若频繁替换，合成比直接保存参数增加了平方级开销，不宣称所有操作组合都更快。

## 正确性与复杂度

两个分支的三角系统分别给出满足特解方程的基函数，线性组合保留方程。加入满足齐次递推的指数项后满足初值，因此由递推解的唯一性，公式就是所求数列。替换只重算当前系数组合，不会沿用先前数列的项。

设 $Q_0$ 为查询次数、$Q_1$ 为替换次数，$N_{\max}$ 为被查询的最大下标。包含模逆元幂计算的预处理时间为 $O((k+1)^3+(k+1)^2\log P)$ ；后续时间为 $O((Q_1+1)(k+1)^2+Q_0(k+1+\log(N_{\max}+1)))$ ，空间 $O((k+1)^2)$ .所有输入负数先规范到 $[0,P-1]$ .

## 补充解法

有限差分与 Newton 二项式基底把特解方程化为相邻系数关系，空间为 $O(k+1)$ ，预处理为 $O(k+1+\log P)$ ；替换和查询的渐进阶与标程相同。二项式求值与系数转换有不同常数，作为空间更低的并列方案保留。

[完整题解与测量](solution-alternative-newton.zh.md) · [计算程序](alternative-newton.cpp)