# 某不科学的多重前缀求和: 题解

## 方法与贡献

出题人解法把多项式转换到上升二项式基底，使每次前缀求和变成基底下标加一。Codex（GPT-6）用相邻次数递推把转换降到二次时间和线性空间，并用批量求逆计算相邻组合数。首选实现见 [std.cpp](std.cpp)。出题人的逐单项式三角消元有[完整题解](solution-alternative.zh.md)和 [alternative.cpp](alternative.cpp)，同样支持完整范围。

以下运算都在质数 $p=2147483647$ 下进行。定义

$$B_0(x)=1,\qquad B_j(x)=\binom{x+j-1}{j}\quad(j\ge1)$$

## 把多重求和变成一次组合数求值

由组合数的相邻差恒等式，对所有 $j\ge0$ 有

$$\sum_{x=1}^{n}B_j(x)=B_{j+1}(n)$$

其中 $j=0$ 时就是常数一的和等于 $n$ .如果输入多项式表示成 $P(x)=\sum_{j=0}^{k}w_jB_j(x)$ ，重复前缀求和 $m$ 次后，答案为

$$\sum_{j=0}^{k}w_j\binom{n+m+j-1}{m+j}\pmod p$$

所以不需要真的执行 $m$ 层递归，也不需要保存长度为 $n$ 的数列。

## 二次时间的基底转换

基底满足

$$xB_j(x)=(j+1)B_{j+1}(x)-jB_j(x)$$

维护当前单项式 $x^i$ 的基底系数 `Current` ，初始为 $x^0=B_0(x)$ .把 $a_i$ 倍的当前系数累加到 $w$ .然后应用上式得到下一次幂；对 $j=i+1,i,\ldots,1$ 依次执行

$$Current_j\leftarrow j(Current_{j-1}-Current_j)\pmod p$$

最后令 $Current_0=0$ .倒序保证右侧仍是上一次幂的系数；原先不存在的最高项按零处理。每一层只扫描线性个系数，总工作量为 $O(k^2)$ ，只需两个长度 $k+1$ 的数组。

## 组合数及批量求逆

先计算

$$C_0=\binom{n+m-1}{m}=\frac{n(n+1)\cdots(n+m-1)}{m!}$$

分别连乘分子和分母，再对分母做一次快速幂求逆，耗时 $O(m+\log p)$ .之后用

$$C_j=C_{j-1}\frac{n+m+j-1}{m+j}$$

递推。对连续的分母 $m+1,\ldots,m+k$ ，先算前缀积 $D_j$ .求一次 $D_k^{-1}$ ，再倒序恢复每个分母的逆元：当前逆积乘以 $D_{j-1}$ 就是 $(m+j)^{-1}$ ，之后乘回 $m+j$ 得到前一个逆积。这样只需 $O(k+\log p)$ 时间。

最大 $n+m+k-1$ 为 $2010000299<p$ ，所有涉及的正整数阶乘因子都小于模数，逆元存在。两次取模之间的 64 位乘积小于 $p^2<2^{63}$ .

## 正确性与复杂度

乘以 $x$ 的基底恒等式保证 `Current` 归纳地表示每个单项式；加权累加后 $w$ 就表示完整输入多项式。每次前缀求和把每项下标加一，重复 $m$ 次得到目标组合数表达式。乘积、逆元及相邻比值恰好计算这些组合数，因此输出正确。

标准程序时间 $O(m+k^2+\log p)$ ，辅助空间 $O(k)$ .三角消元程序需要 $O(m+k^3+k\log p)$ 时间和 $O(k^2)$ 空间，可作为理解基底转换的另一种直接方法；首选程序在转换的时间和空间上都有明确优势。