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

Codex（GPT-6）将多项式离散求和的线性变换用于本题，给出三角预处理、系数更新、实现及验证；离散差分、二项式展开与模逆元均为通用方法。

## 找一个能望远镜消去的多项式

为避免与模数混淆，记当前负载多项式为 $B(x)=\sum_{j=0}^k b_jx^j$ .希望构造 $Q(x)$ ，使

$$aQ(x+1)-Q(x)=B(x).$$

将 $x=i$ 代入并乘以 $a^i$ ，再累加，得到

$$F(n)=a^{n+1}Q(n+1)-aQ(1).$$

因此只需维护多项式 $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$ 的系数，有

$$(a-1)q_t+a\sum_{h=t+1}^{j}\binom ht q_h=[t=j].$$

右侧的 $[t=j]$ 在两者相等时为一，否则为零。由高次到低次解三角方程，除以 $a-1$ 使用模逆元。

当 $a=1$ 时，差分会降低一次次数。改取次数 $j+1$ 、常数项为零，按

$$(t+1)q_{t+1}+\sum_{h=t+2}^{j+1}\binom ht q_h=[t=j]$$

从高到低解。所除的 $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](std.cpp) 支持全部操作分布。[幂矩递推方案](solution-alternative.zh.md) 在仅修改系数时可做到每次常数时间，但频繁修改上界时更慢，公开为备用实现。

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