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

无除法的块拼接¶

Codex（GPT-6）补充该方法及 alternative.cpp。等比求导的首选解法见主题解。令 \(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)\) .它避免逆元和特殊公比分支，代价是每层要维护多个乘积；与首选公式都是完整范围算法。