Yet Another Prefix Sum Problem

设 $X_i=A+iD$。若 $X_i$ 是 $p$ 的倍数，则 $X_i^{X_i}\equiv0\pmod p$。否则，根据费马小定理，可以将指数对 $p-1$ 取模。

按照 $i=r+tp$ 对下标分组，其中 $0\le r<\min(N,p)$。第 $r$ 组的项数是

$$m_r=\left\lfloor\frac{N-1-r}{p}\right\rfloor+1$$

$X_r$ 可能超过有符号 $64$ 位整数范围，因此只需计算

$$b_r=(A\bmod p+(rD)\bmod p)\bmod p, \qquad e_r=(A\bmod(p-1)+(rD)\bmod(p-1))\bmod(p-1).$$

若 $b_r=0$，该组所有项均为 $0$。否则，定义

$$C_r=b_r^{e_r}\bmod p,\qquad R_r=b_r^{D\bmod(p-1)}\bmod p$$

于是下标为 $i=r+tp$ 的项满足

$$(A+iD)^{A+iD}\equiv C_rR_r^t\pmod p$$

注意首项是 $b_r^{e_r}$，一般不等于 $b_r^{b_r}$：底数对 同余并不意味着指数对 同余。

若 $R_r=1$，组内之和为 $C_rm_r$；否则为

$$C_r\frac{R_r^{m_r}-1}{R_r-1}\pmod p$$

除法通过模逆元完成。由于 $b_r\ne0$，所以 $R_r\ne0$，幂指数可以对 取模。可以在线性时间内预处理从 到 的逆元。

将各组结果相加。分组数量不超过 $\min(N,p)$，每组计算模幂需要 $O(\log p)$ 时间，总时间复杂度为 $O(p+\min(N,p)\log p)$，空间复杂度为 。在乘法前先对操作数取模，即可保证所有中间值处于有符号 位整数范围内。

Solution written by GPT6