快速幂

在计算数的幂时，常规的做法是进行多次连乘运算，例如计算 a 的 n 次幂，就需要连乘 n 次：a a … * a。然而，当指数 n 很大时，这样的计算方式效率很低，会进行大量的重复计算。

快速幂算法（Exponentiation by Squaring）是一种优化计算幂的方法，它通过将指数 n 分解成二进制形式，并利用幂的性质进行计算，从而减少了不必要的重复计算，提高了计算效率。

模板

1
2
3
4
5
6
7
8
9
10
int MOD = (int)1e9 + 7;
long pow(long x, int n) {
    long res = 1;
    while (n != 0) {
        if (n % 2 != 0) res = res * x % MOD;
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private long[][] multi(long a[][], long b[][], int n) {
    long res[][] = new long[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}
public long[][] pow(long matrix[][], long k, int n) {
    long res[][] = new long[n][n];
    for (int i = 0; i < n; i++) {
        res[i][i] = 1;
    }
    if (k == 0) return res;
    long newMatrix[][] = multi(matrix, matrix, n);
    res = pow(newMatrix, k/2, n);
    if (k % 2 == 1) {
        res = multi(res, matrix, n);
    }
    return res;
}

题解