Grox的序列六题解¶
出题人解法：预处理多项式特解的系数矩阵，以多项式与指数项表示递推。 Codex（GPT-6）将 \(\beta=1\) 的特解显式写成差分求和分支，保留负数与零次幂的处理，并在替换参数时合成系数，使查询从逐个基函数求值改为对一个多项式求值。
多项式特解¶
所有计算在模 \(P=1000000007\) 下进行。令
当 \(\beta\ne1\) 时，寻找次数不超过 \(k\) 的多项式 \(g(n)\) ，使
若 \(g(n)=\sum_{j=0}^k c_j n^j\) ，比较 \(n^d\) 的系数得到
这是从高次数到低次数求解的三角系统，且 \(1-\beta\) 可逆。先为每个基函数 \(T(n)=n^i\) 求出一组系数，记对应多项式为 \(g_i(n)\) .
对任意参数，以线性组合 \(g(n)=\sum_i a_i g_i(n)\) 得到特解，进而
后一项满足齐次递推，零下标项等于 \(\alpha\) ，所以公式满足完整初值与递推。模幂在这里遵循 \(\beta^0=1\) ，包括 \(\beta=0\) ，保证查询零下标得到初值；\(n>0,\beta=0\) 则指数项为零。
当 beta 等于一¶
此时 \(1-\beta\) 不可逆，改用次数不超过 \(k+1\) 且 \(g(0)=0\) 的离散原函数：
系数系统为
从 \(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)\) ；替换和查询的渐进阶与标程相同。二项式求值与系数转换有不同常数，作为空间更低的并列方案保留。