简介
快速幂是能快速计算一个幂的方案，他可以作用于所有满足结合律、封闭性的二元运算，即半群
定义
不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时，不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$
快速幂核心思想
在半群中，只要$k=u+v$一定有$x^k=x^u\circ x^v$.
所以我们可以把k看作一个二进制数，把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$
这里最多分解为$\log_2(k)$个元素，而且每个元素可以由前k个元素获取，所以只需要进行$log_2(k)$次二元计算即可的到最终答案。
代码
1 | T qpow(T a,int k){ |
加法模群快速幂
在加法模群中，getE()定义为0，因为任何数加上0得到自身。binaryOp为二元运算$binaryOp(x,y)=(x+y)\mod p$。
乘法模群快速幂
在乘法模群中，getE()定义为1，因为任何数乘以1得到自身。binaryOp为二元运算$binaryOp(x,y)=(x\cdot y)\mod p$。
矩阵乘法模群快速幂
在矩阵乘法模群中，getE()定义为矩阵的单位元，即对角线全为1的对角矩阵。binaryOp为普通矩阵模乘。
无理数乘法快速幂
很多时候我们需要用到无理数，即设一个无理数$y=\sqrt{(c_1)}\cdot x_1+x_2$, 其中$x$为变量，$c$均为常量，一个无理数可以被唯一标识为一个二元组$(x_1,x_2)$,
这时候单位元是getE()=$(0,1)$, binaryOp为普通无理数乘法。
置换群快速幂
在置换中，单位元为$h=\begin{pmatrix}
1 & 2 & 3 &… &n\
1 & 2 & 3 &… &n
\end{pmatrix}$ ,binaryOp为普通置换乘法。
十进制快速幂
有的时候，给你的k是一个10进制大数，由于我们朴素的快速幂需要使用二进制的k（后面有移位），所以会遇到一些麻烦。
当然，最简单的就是直接分解为十进制乘法。
$x^k=x^{10^{p_1}}\circ x^{10^{p_2}}\circ x^{10^{p_3}}\circ \circ \circ x^{10^{p_n}}$
道理都是一样的。这里最多分解出$\log^{10}(k)$个元素，每个$x^{10^1}$可以从前一项直接运算推导。最多进行$\log^{10}(k)$次计算
代码
矩阵快速幂
1 | typedef long long ll; |
十进制快速幂
1 |
|
