某不科学的多项式加权几何和的修改 — 题解¶
Codex（GPT-6）将多项式离散求和的线性变换用于本题，给出三角预处理、系数更新、实现及验证；离散差分、二项式展开与模逆元均为通用方法。
找一个能望远镜消去的多项式¶
为避免与模数混淆，记当前负载多项式为 \(B(x)=\sum_{j=0}^k b_jx^j\) .希望构造 \(Q(x)\) ，使
将 \(x=i\) 代入并乘以 \(a^i\) ，再累加，得到
因此只需维护多项式 \(Q\) ，每次用 Horner 法求两处值，加一次快速幂即可。
对每个单项式预处理一列¶
先求 \(Q_j(x)\) ，满足 \(aQ_j(x+1)-Q_j(x)=x^j\) .由于变换线性，任意当前系数对应 \(Q(x)=\sum_jb_jQ_j(x)\) .修改 \(b_j\) 时，只需给 \(Q\) 的系数加上 \(\Delta b_j\) 倍的预处理列。
当 \(a\ne1\) 时，设 \(Q_j(x)=\sum_{h=0}^j q_hx^h\) .比较 \(x^t\) 的系数，有
右侧的 \([t=j]\) 在两者相等时为一，否则为零。由高次到低次解三角方程，除以 \(a-1\) 使用模逆元。
当 \(a=1\) 时，差分会降低一次次数。改取次数 \(j+1\) 、常数项为零，按
从高到低解。所除的 \(1,\ldots,k+1\) 都小于素模数，可以预先算出逆元。\(a=0\) 也适用第一种三角式，最终答案自然为零，无需对零求逆。
正确性与复杂度¶
每列的三角系统对角均可逆，逐项比较系数保证恒等式成立。线性组合及系数增量维护保证当前 \(Q\) 始终对应当前 \(B\) .望远镜求和式因此准确返回目标和；上界更新不会影响预处理列。
预处理二项式与逆元后，全部列用 \(O(k^3)\) 时间、\(O(k^2)\) 空间；建立初始 \(Q\) 用 \(O(k^2)\) .每次系数修改及多项式求值为 \(O(k)\) ，上界变化时快速幂为 \(O(\log n)\) ，故总时间 \(O(k^3+m(k+\log n))\) ，空间 \(O(k^2)\) .模数固定；求一个一般逆元还需一次 \(O(\log P)\) 快速幂。相乘后及时取模，64 位整数足够。
std.cpp 支持全部操作分布。幂矩递推方案 在仅修改系数时可做到每次常数时间，但频繁修改上界时更慢，公开为备用实现。