快速幂

  • 快速幂是一种高效的指数运算方法，通过指数折半或二进制位运算减少计算次数。
  • 如下：快速计算base的power次方
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
// base：底数，power：指数
long long FastPower(int base, int power)
{
    long long result = 1;
    while (power)
    {
        // 表示按位与操作，相当于power % 2
        if (power & 1) result *= base;
        // 右移运算符，相当于 power /= 2
        power >>= 1;
        base *= base;
    }
    return result;
}

// 快速幂取模运算
long long FastPower(int base, int power, int model)
{
    long long result = 1;
    while (power)
    {
        if (power & 1) result = (result * base) % model;
        power >>= 1;
        base = (base * base) % model;
    }
    return result;
}

矩阵快速幂

  • 例：降低斐波那契（Fibonacci）数列的时间、空间复杂度

推导过程

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 矩阵相乘运算
// x，y：需要计算的两个矩阵
vector<vector<int>> MatrixMul(vector<vector<int>>& x, vector<vector<int>>& y)
{
    int sizeARow = x.size();
    int sizeAColumn = x[0].size();
    int sizeBColumn = y[0].size();
    vector<vector<int>> result(sizeARow, vector<int>(sizeBColumn, 0));
    for (int i = 0; i < sizeARow; ++i)
    {
        for (int j = 0; j < sizeBColumn; ++j)
        {
            for (int k = 0; k < sizeAColumn; ++k)
            {
                result[i][j] += x[i][k] * y[k][j];
            }
        }
    }
    return result;
}

// 矩阵相乘取模运算
vector<vector<int>> MatrixMul(vector<vector<int>>& x, vector<vector<int>>& y, int model)
{
    int sizeARow = x.size();
    int sizeAColumn = x[0].size();
    int sizeBColumn = y[0].size();
    vector<vector<int>> result(sizeARow, vector<int>(sizeBColumn, 0));
    for (int i = 0; i < sizeARow; ++i)
    {
        for (int j = 0; j < sizeBColumn; ++j)
        {
            for (int k = 0; k < sizeAColumn; ++k)
            {
                result[i][j] = (result[i][j] + (x[i][k] % model) * (y[k][j] % model)) % model;
            }
        }
    }
    return result;
}

// 计算一个2 * 2矩阵的n次方
vector<vector<int>> MatrixFastPower(int n)
{
    --n;
    // 初始矩阵
    vector<vector<int>> matrix = {{1, 1}, {1, 0}};
    // 初始矩阵的n - 1次方
    vector<vector<int>> result = {{1, 0}, {0, 1}};
    while (n)
    {
        if (n & 1) result = MatrixMul(result, matrix);
        n >>= 1;
        matrix = MatrixMul(matrix, matrix);
    }
    return result;
}