GitHub 源文件 Markdown English

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

思路

记模数为 \(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 中实现，短位置、长轮数的输入走卷积核分支。

方法来源与验证

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