# 某不科学的等差等比加权和: 补充解法

## 无除法的块拼接

Codex（GPT-6）补充该方法及 [alternative.cpp](alternative.cpp)。等比求导的首选解法见[主题解](solution.zh.md)。令 $q=c^b\bmod p$ ，对长度为 $L$ 的块保存

$$P=q^L,\qquad S=\sum_{j=0}^{L-1}q^j,\qquad W=\sum_{j=0}^{L-1}jq^j$$

拼接前块 $A$ 与后块 $B$ ，后块所有幂需要乘上 $P_A$ ，下标还需增加 $L_A$ ，因此

$$P=P_AP_B,\quad S=S_A+P_AS_B,\quad W=W_A+P_A(W_B+L_AS_B)$$

长度相加，所有数值按 $p$ 取模。空块为 $(L,P,S,W)=(0,1,0,0)$ ，单项块为 $(1,q,1,0)$ .像快速幂一样不断将当前块与自己拼接，并按长度二进制位累加到结果块，得到 $L=r-l+1$ 的统计量。

换元 $i=l+j$ 后答案为

$$c^dq^l\bigl((a+bl)S+bW\bigr)\pmod p$$

拼接式逐项覆盖前后两段，保持四个量的定义；二进制拼接得到所需长度，再由换元式得到正确区间和。整个方法对 $q=1$ 也直接成立。

时间 $O(\log(b+1)+\log(d+1)+\log(l+1)+\log(r-l+2))$ ，辅助空间 $O(1)$ .它避免逆元和特殊公比分支，代价是每层要维护多个乘积；与首选公式都是完整范围算法。