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

## 方法与贡献

出题人解法是对有限等比级数求导，得到带下标权值的求和公式。Codex（GPT-6）补全模意义下公比为一的分支，并整理标准 C++17 实现。首选程序见 [std.cpp](std.cpp)，无除法的[块拼接方案](solution-alternative.zh.md)及 [alternative.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}$ 的乘积，仍在范围内。实际运算按代码中的次序及时取模。块拼接方案省去逆元，但增加每层维护的量；两种方案均覆盖完整输入范围。