# 某不科学的多重等比求和：按较小维度计算

## 思路

记模数为 $p=2147483647$ ，前缀求和算子为 $S$ .直接展开需要遍历多个求和下标；这里在 $n,m$ 中选择较小的维度。

### 当位置数较少：二项式卷积核

初始第 $x$ 项经过 $m$ 次前缀求和后，在位置 $n$ 的系数是

$$\binom{n-x+m-1}{m-1}.$$

这可以从一轮求和的系数一出发，用 Pascal 恒等式逐轮证明；也等于把 $n-x$ 个增量分配到 $m$ 个阶段的方案数。因此

$$F_m(n)=\sum_{t=0}^{n-1}\binom{m+t-1}{t}F_0(n-t).$$

令权重 $w_0=1$ ，递推 $w_{t+1}=w_t(m+t)/(t+1)$ .当 $a\ne1$ 时，

$$F_0(x)=\frac{a^{2x+1}-a^x}{a-1}.$$

从 $x=n$ 开始递减，用 $a^{-1}$ 和 $a^{-2}$ 更新两项幂。$a=1$ 时直接取 $F_0(x)=x+1$ .这条分支遍历 $n$ 项。

### 当轮数较少：对轮数递推

定义 $H_t(n,q)=S^t(q^x)(n)$ .几何级数给出

$$S(q^x)(n)=\frac{q}{q-1}(q^n-1).$$

再作用 $S^{t-1}$ ，并利用 $S^{t-1}(1)(n)=\binom{n+t-2}{t-1}$ ，得到

$$H_0(n,q)=q^n,\qquad H_t(n,q)=\frac{q}{q-1}\left(H_{t-1}(n,q)-\binom{n+t-2}{t-1}\right).$$

同时维护 $q=a$ 与 $q=a^2$ 两条递推，最后组合为

$$F_m(n)=\frac{aH_m(n,a^2)-H_m(n,a)}{a-1}.$$

在本题范围内，$a\ne1$ 时 $a^2\not\equiv1\pmod p$ ：域中的两个平方根为一与 $p-1$ ，后者大于输入上界。所有分母均可逆。若 $a=1$ ，使用

$$F_m(n)=\binom{n+m}{m+1}+\binom{n+m-1}{m}.$$

这是对 $x$ 和常数一分别重复求和的结果。依次计算二项式系数即可。

## 正确性

卷积核分支精确计算每个初始项在最终值中的重数；轮数分支由前缀算子的线性和几何级数恒等式逐层得到同一个值。单位底数公式覆盖其余情况。根据 $n\le m$ 选择第一条分支，否则选择第二条，所以每个合法输入都由一个正确分支处理。

## 实现与复杂度

所有运算均在模域内完成。线性预处理所需小整数的逆元：$\operatorname{inv}(i)=-(p\mathbin{//}i)\operatorname{inv}(p\bmod i)\bmod p$ .这里 $n+m<p$ ，且预处理长度不超过 $\min(n,m)+1$ ，不会遇到不可逆的分母。使用有符号 64 位整数乘法，每次乘积后立即取模；两个剩余相乘小于 $p^2<2^{63}$ .

时间为 $O(\min(n,m)+\log p)$ ，额外空间为 $O(\min(n,m))$ .两种求和方向都在 [std.cpp](std.cpp) 中实现，短位置、长轮数的输入走卷积核分支。

## 方法来源与验证

几何级数、二项式卷积核与有限差分恒等式是经典方法。GPT-6 完成组合应用、推导、实现和独立检查；可用材料未提供有效的出题人解法。朴素多轮前缀求和用于小规模核对。正式数据还用部分分式展开或独立权重计算核对，包含单位底数和两个分支交界。性能见[测量记录](../../../docs/benchmark-R24.json)。