快速幂（二进制取幂，binary exponentiation）可以在 O(\log n) 时间内求得 a^n 或 a^n \bmod p 的值（n \in \mathbb{N}^+）。

整数快速幂

算法

计算 a^n 时，先将 n 做二进制展开，得到：

于是有

而 a^{2^i} = \left(a^{2^{i - 1}}\right)^2 可递推计算。这样，只需要记录变量 base = a，每次将 base 翻倍，然后当 n 的第 i 个二进制位为 1 时，在结果乘上 base，即可计算出幂。

using ull = unsigned long long;

ull binexp(ull a, ull n)
{
    ull result = 1, base = a;
    while (n)
    {
        if (n & 1)
        {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        n >>= 1;
    }
    return result;
}

龟速乘

在不溢出 long long 的情况下，计算 a \times b \bmod m 的值。

方法类似于快速幂，对 b 二进制拆位，然后对 a 做加法。这样做的复杂度是 O(\log b) 的，一般相当于带上一个 64 的常数。

ull smul(ull a, ull b) // slow mul
{
    ull ret = 0;
    while (b)
    {
        if (b & 1)
        {
            ret = (ret + a) % P;
        }
        a = 2 * a % P;
        b >>= 1;
    }
    return ret;
}

其他快速幂

矩阵快速幂

矩阵同样可以应用快速幂。两个 m 阶矩阵相乘的复杂度是 O(m^3)，所以矩阵快速幂计算 A^n 的复杂度是 O(m^3 \log n)。

一般快速幂

只要保证运算 \odot 有结合律，当计算 \bigodot\limits_{i=1}^n a_i 时，都可以应用快速幂算法，用 O(\log n) 次 \odot 运算得到结果。这个过程实质上就是 （链接未公开） 的应用。

例如，置换是有结合律的运算，因此同一个置换对数列作用 n 次时，可以用快速幂计算出 n 次复合置换，再将复合置换应用在数列上。

例题

ABC 367 E

https://atcoder.jp/contests/abc367/tasks/abc367_e

给定一个长度为 n 的数列 a，和一个长度为 n 的下标数列 x，满足 x_i \in \{1, 2, \dots, n\}。每次令 b_i = a_{x_i}，然后令 a_i = b_i，得到一个新的数列 a，重复 k 次，求最终得到的数列 a。

可以发现取下标运算 b_i = a_{x_i} 是一个有结合律的运算，它相当于令

其中 M 是一个 n \times n，且每一行只有一个 1 的矩阵，a, b 均视为列向量。

这个运算也可以看做是在内向基环森林（也叫 （链接未公开））上求一个节点的 k 级后继。或者可以看做一种广义的置换，在这种置换中允许结果出现重复元素，将两个数映射到同一个数上。

矩阵乘法具有结合律，所以可以倍增快速幂。注意由于这个矩阵的特殊性，计算矩阵乘法只需要 O(n) 的复杂度，不需要 O(n^3)。