# 某不科学的多重前缀求和: 补充解法

## 出题人解法：逐单项式三角消元

出题人给出将单项式展开到上升二项式基底的消元方法；Codex（GPT-6）将其实现为 [alternative.cpp](alternative.cpp)，并加入组合数分母批量求逆。求和恒等式、组合数求值和更省时空的递推见[主题解](solution.zh.md)。

先按

$$B_j(x)=\frac{x+j-1}{j}B_{j-1}(x)$$

建立每个 $B_j$ 的普通幂系数表，$B_0=1$ .每次只乘一个一次多项式，共 $O(k^2)$ 个系数操作，除以 $j$ 用模逆元。$B_j$ 的最高次系数是 $1/j!$ .

对每个 $x^i$ ，令剩余多项式最初为 $x^i$ ，从 $j=i$ 到零处理。若其 $x^j$ 系数为 $r_j$ ，取基底系数 $r_jj!$ ，并从剩余多项式中减去这一倍的 $B_j$ .最高项被消去，且不会改变更高次数，因为 $B_j$ 的次数只有 $j$ .降到零后剩余多项式为零，得到完整且正确的展开。把这一组系数乘上 $a_i$ ，累加到总权重即可。

最后对每个基底使用 $m$ 次求和后变为 $B_{j+m}(n)$ 的恒等式，计算和输出答案。每个消元步骤保持“原单项式等于已确定基底部分加剩余多项式”，所以最终展开正确；线性求和保证完整答案正确。

实现的时间为 $O(m+k^3+k\log p)$ ，空间 $O(k^2)$ .其中逐个求 $1,\ldots,k$ 的逆元占 $O(k\log p)$ ，所有单项式的消元占三次时间。这个方法完整有效，但递推转换在时间和空间上都更省，故后者为首选。