就是不预处理，每次算 $n^{n-2}$ 的时候快速幂就线性。

因为设环长为 $l_1,l_2,\dots l_m$，则有 $\sum l_i=n$。

而快速幂的复杂度为 $\sum\log l_i\le \sum l_i=n$，于是所有快速幂的复杂度加起来就是线的啦。