整理各种实(wai)用(men)技(xie)巧(dao)
光速幂
对于形如 \(a^b mod\ p\) 的柿子，常见的处理方法是快速幂 \(O(0)-O(\log b)\)（预处理-询问）。
如果某些题目要求单次询问 \(O(1)\)，这时候就可以请出光速幂 \(O(\sqrt n)-O(1)\)，但是注意光速幂要求底数和模数都固定，所以应用不广。
具体而言，我们将幂指数分成 \(k\) 块,预处理出 \(a^s,a^{2s}...,a^{ks}\) 和
\(a,a^2...a^{s-1}\)，这样就有
\[a^b = a^{\lfloor\frac{b}{s}\rfloor \times s+{b\ mod\ s}} \mod p
\]
如果 \(p\) 是素数直接预处理到 \(p-1\) 即可。（或者到 \(φ(p)\)，但没必要）。
code:
点击查看代码
void predeal(int x){
sq = sqrt(mod);
ph[0][0] = ph[0][1] = 1;
for(int i = 1; i <= sq; i++)
ph[i][0] = ph[i-1][0] * x % mod;
ph[1][1] = ph[sq][0];
for(int i = 2; i <= sq; i++)
ph[i][1] = ph[i-1][1] * ph[1][1] % mod;
return;
}
int power(int x){return ph[x/sq][1] * ph[x%sq][0] % mod;}
基数排序
这是个非常玄学的东西，甚至能排 \(1e8\) 的数列。