某不科学的等差等比加权和: 题解¶

方法与贡献¶

出题人解法是对有限等比级数求导，得到带下标权值的求和公式。Codex（GPT-6）补全模意义下公比为一的分支，并整理标准 C++17 实现。首选程序见 std.cpp，无除法的块拼接方案及 alternative.cpp 提供另一种同阶方法。

令 \(p=10^9+7\) ，\(q=c^b\bmod p\) .目标可以写为

\[ c^d\sum_{i=l}^{r}(a+bi)q^i\pmod p \]

等比求和与带权和¶

定义 \(S(n)=\sum_{i=1}^{n}q^i\) 和 \(T(n)=\sum_{i=1}^{n}iq^i\) ，空前缀的两者均为零。若 \(q\ne1\) ，有限等比求和公式以及对公比的形式求导给出

\[ S(n)=\frac{q^{n+1}-q}{q-1} \]

\[ T(n)=\frac{nq^{n+2}-(n+1)q^{n+1}+q}{(q-1)^2} \]

这里每个除法都表示模 \(p\) 的乘法逆元。因为 \(p\) 是质数且 \(q-1\not\equiv0\pmod p\) ，逆元可用快速幂 \((q-1)^{p-2}\bmod p\) 求得。平方这个逆元即可处理第二式。

令 \(H(n)=aS(n)+bT(n)\) .区间答案就是 \(c^d(H(r)-H(l-1))\bmod p\) ，减法结果应规范到 \([0,p-1]\) .

若 \(q=1\) ，每一项的等比部分均为一，直接计算

\[ c^d\left(a(r-l+1)+b\frac{(l+r)(r-l+1)}{2}\right)\pmod p \]

注意这个条件检查的是 \(c^b\bmod p\) .例如 \(c=4,b=500000003\) 时，公比也等于一。此分支中二的逆元存在，可以使用 \((p+1)/2\) .

正确性证明¶

对等比恒等式逐项求导后乘以 \(q\) ，左侧恰好是 \(T(n)\) ；整理右侧得到所给带权公式。因此在非一公比下，\(H(n)\) 精确等于从一到 \(n\) 的目标前缀和，前缀相减只保留 \(l\) 到 \(r\) 的项。公比为一时，公式直接来自等差数列的项数及下标之和。再乘上共同因子 \(c^d\) ，两种情形都得到题目要求的值。

复杂度与实现¶

每次询问使用常数次快速幂，时间为 \(O(\log(b+1)+\log(d+1)+\log(r+1)+\log p)\) ，辅助空间 \(O(1)\) .所有询问独立处理。

使用有符号 64 位整数。未取模的原始乘积如 \(bl\) 不超过 \(10^{18}\) ；求和步骤中至多相加两个约 \(10^{18}\) 的乘积，仍在范围内。实际运算按代码中的次序及时取模。块拼接方案省去逆元，但增加每层维护的量；两种方案均覆盖完整输入范围。