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

方法与贡献¶

出题人解法把多项式转换到上升二项式基底，使每次前缀求和变成基底下标加一。Codex（GPT-6）用相邻次数递推把转换降到二次时间和线性空间，并用批量求逆计算相邻组合数。首选实现见 std.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)\) 空间，可作为理解基底转换的另一种直接方法；首选程序在转换的时间和空间上都有明确优势。