某不科学的多项式加权几何和的修改 — 补充题解¶
Codex（GPT-6）推导并实现本题的幂矩递推和常数时间系数更新。见 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 秒时限，故是备用方案；完整范围默认使用三角变换方案。