trick

整理各种实(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}\)，这样就有

如果 \(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\) 的数列。