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

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

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

先按

\[ 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)\) ，所有单项式的消元占三次时间。这个方法完整有效，但递推转换在时间和空间上都更省，故后者为首选。