快速幂

在计算数的幂时，常规的做法是进行多次连乘运算，例如计算 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;
}
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
26
27
28
// 非方阵的矩阵相乘函数写法（长度不用相等）
// `m*l` * `l*n` = `m*n`
private long[][] multi(long a[][], long b[][]) {
    long res[][] = new long[a.length][b[0].length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < b[0].length; j++) {
            for (int k = 0; k < a[0].length; 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 = matrix.length;
    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);
    res = pow(newMatrix, k/2);
    if (k % 2 == 1) {
        res = multi(res, matrix);
    }
    return res;
}

矩阵乘法时，先进行k的循环，再进行j的循环，当a[i][k]为0时可以直接跳过，在矩阵元素包含较多0时可以节省较多时间

1
2
3
4
5
6
7
8
9
10
11
12
13
private long[][] multi(long a[][], long b[][], int n) {
    long res[][] = new long[n][n];
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (a[i][k] == 0) continue;
            for (int j = 0; j < n; j++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}

题解