# 某不科学的多项式加权几何和的修改 — 补充题解

Codex（GPT-6）推导并实现本题的幂矩递推和常数时间系数更新。见 [alternative.cpp](alternative.cpp)。

## 保存所有幂矩

固定当前 $n$ ，定义 $S_j(n)=\sum_{i=1}^n a^i i^j$ ，则答案是 $\sum_jb_jS_j(n)$ .修改一个系数时，答案直接增加 $\Delta b_jS_j(n)$ ，耗时 $O(1)$ .只有上界变化时才重算全部幂矩。

当 $a\ne1$ ，对相邻项作差并展开 $(i-1)^j$ ，得到

$$(1-a)S_j=a[ j=0]+\sum_{t=0}^{j-1}(-1)^{j-t+1}\binom jt S_t-a^{n+1}n^j.$$

特别地 $S_0=(a-a^{n+1})/(1-a)$ .按 $j$ 从小到大递推；边界 $a[j=0]$ 不能漏掉。$a=0$ 时该式仍成立。

当 $a=1$ ，利用 $(i+1)^{j+1}-i^{j+1}$ 的望远镜和，得到

$$S_j=\frac{(n+1)^{j+1}-1-\sum_{t=0}^{j-1}\binom{j+1}{t}S_t}{j+1}.$$

所有除法使用已预处理的模逆元，连续的 $n^j$ 与 $(n+1)^{j+1}$ 用乘法递增。

## 正确性、复杂度与地位

两个递推均由定义的有限和恒等变形而来，且只依赖更低次幂矩，归纳保证所有 $S_j$ 正确。答案的内积及单系数增量因此正确。

设上界修改次数为 $q$ ，预处理二项式用 $O(k^2)$ ，一次重算用 $O(k^2+\log n+\log P)$ ，系数修改用 $O(1)$ ；空间 $O(k^2)$ .在系数更新占多数时它避免每次维护整个多项式，但全为上界修改时退化到 $O(mk^2)$ .本机正式压力五轮最慢中位数约 0.702 秒，超过 0.5 秒时限，故是备用方案；完整范围默认使用[三角变换方案](solution.zh.md)。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R33.json)