二进制快速幂

二进制快速幂（简称BE）是一种可以加速幂运算计算的技术。对于朴素的幂运算 ，时间复杂度是 ，而使用二进制快速幂，时间复杂度降为 。
让我们从一个例子开始，

假设 是一个32位整数，这意味着最多我们只需要计算32次，并检查 是否包含在内。

def fast_power(a, exp):
    if exp == 0:
        return 1
    if exp == 1:
        return a
    base = a
    result = 1
    while exp > 0:
        if exp & 1:
            result *= base
        base *= base
        exp >>= 1
    return result

矩阵快速幂

def matrix_fast_power(A, n):
    ans = I  # 单位矩阵
    while n:
        if n & 1:
            ans = ans * A
        A = A * A
        n >>= 1
    return ans

矩阵快速幂主要用于线性递归计数问题，以及一些状态转移方程是线性递归关系的动态规划问题。有些计数问题可以通过手动推导小规模的n来观察模式，并猜测递归关系。如果这个递归关系是线性的，那么它可以转化为矩阵幂问题，并使用矩阵快速幂加速计算。