🌐 中文 English
This article aims to explain how to implement fast exponentiation for multiplication and matrices. The test links for this chapter are: Fast Exponentiation for Multiplication: https://www.luogu.com.cn/problem/P1226 1D k-order Matrix Fast Exponentiation: https://leetcode.cn/problems/n-th-tribonacci-number/ kD 1-order Matrix Fast Exponentiation: https://leetcode.cn/problems/count-vowels-permutation/
Introduction to Fast Exponentiation
Fast exponentiation is an algorithm used to quickly compute powers. It utilizes the binary representation of the exponent to reduce the number of multiplication operations. It is mainly divided into two types:
- Fast Exponentiation for Multiplication: Used to compute power operations of the form
a^b. - Fast Exponentiation for Matrices: Used to compute matrix powers. Matrix fast exponentiation is further divided into 1D k-order matrix fast exponentiation and kD 1-order matrix fast exponentiation.
Time Complexity of Fast Exponentiation
The time complexity of fast exponentiation is O(log n), where n is the exponent. Traditional exponentiation requires n multiplication operations, while fast exponentiation significantly reduces the number of multiplication operations by continuously dividing the exponent by 2, thereby improving computational efficiency. Therefore, fast exponentiation always involves the operation of repeatedly squaring and adding numbers.
Fast Exponentiation for Multiplication
Let’s first look at fast exponentiation for multiplication: https://www.luogu.com.cn/problem/P1226
The solution is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<vector>
using namespace std;
int power(int a, int b, int p) {
long long ans = 1;
while (b > 0) {
if ((b & 1) == 1) {
ans = (ans * a) % p;
}
a = ((long long)a * a) % p; // Multiplying itself yields 1, 2, 4, 8, 16...
b >>= 1;
}
return ans;
}
int main() {
int a, b, p;
cin >> a >> b >> p;
cout << a << "^" << b << " mod " << p << "=" << power(a, b, p);
return 0;
}
- In fast exponentiation for multiplication, we continuously divide the exponent b by 2 and determine whether the current base a needs to be multiplied into the result ans based on whether the binary digit of the exponent is 1.
For example, when calculating2^10, the binary representation of the exponent 10 is 1010. Reading from right to left, when we encounter the first 1, we multiply the current base 2 into the result ans, then square the base, shift the exponent right by one bit, and continue checking the next binary digit. - When encountering the next 1, we multiply the current base 2 into the result ans, then square the base, shift the exponent right by one bit, and continue checking the next binary digit.
We can observe that each time the exponent is shifted right by one bit, the base is squared once. Therefore, we only need to perform log n multiplication operations to obtain the result.
Fast Exponentiation for Matrices
Matrix fast exponentiation can be seen as an extension of fast exponentiation for multiplication. Fast exponentiation for multiplication is used for 1D 1-order calculations, while matrix fast exponentiation is used for kD 1-order calculations and 1D k-order calculations.
Example Overview of 1D k-order Matrix Fast Exponentiation
Here, the Tribonacci sequence is used as an example. The problem link is: https://leetcode.cn/problems/n-th-tribonacci-number/
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
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>> a, vector<vector<int>> b) {
int n = a.size();
int m = b[0].size();
int k = a[0].size();
vector<vector<int>> ans(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int c = 0; c < k; ++c) {
ans[i][j] += (long long)a[i][c] * b[c][j];
}
}
}
return ans;
}
// Matrix fast exponentiation
vector<vector<int>> power(vector<vector<int>> a, int p) {
int n = a.size();
vector<vector<int>> ans(n, vector<int>(n));
// Create identity matrix
for (int i = 0; i < n; ++i) {
ans[i][i] = 1;
}
while (p > 0) {
if ((p & 1) == 1) {
ans = multiply(ans, a);
}
a = multiply(a, a);
p >>= 1;
}
return ans;
}
int tribonacci(int n) {
// First, handle edge cases where start cannot cover the leftmost values
if (n == 0) return 0;
if (n == 1) return 1;
vector<vector<int>> start = { {1, 1, 0} };
vector<vector<int>> base = {
{1, 1, 0},
{1, 0, 1},
{1, 0, 0}
};
vector<vector<int>> ans = multiply(start, power(base, n - 2));
return ans[0][0];
}
};
The idea is similar to fast exponentiation for multiplication, but the base is extended from 1D 1-order to 1D k-order. The multiplication in fast exponentiation for multiplication becomes the matrix multiplication function multiply in 1D k-order matrix fast exponentiation, used to compute the product of two matrices. Then, a matrix fast exponentiation function power is defined to perform matrix exponentiation. The implementation of this function is also similar to fast exponentiation for multiplication, except the base is replaced with a matrix. We continuously divide the exponent by 2 and determine whether the current base matrix a needs to be multiplied into the result ans based on whether the binary digit of the exponent is 1. The base matrix a continuously squares itself, similar to how the base is handled in fast exponentiation for multiplication.
Underlying Logic Analysis of 1D k-order Matrix Fast Exponentiation
How to Determine It’s 1D k-order Matrix Fast Exponentiation
Its form must satisfy F(n + k) = F(n + k - 1) + F(n + k - 2) + … + F(n + k - k)
Here, k represents the order. Satisfying this formula is the condition for using 1D k-order matrix fast exponentiation. As mentioned in my previous Fibonacci sequence blog, it is an example of 1D k-order matrix fast exponentiation, so I won’t repeat it here.
How to Construct the start and base Matrices
- The values in the start matrix are the leftmost values covering the parameter range from F(n + k - 1), F(n + k - 2), …, F(n + k - k).
Example:
T0 = 0, T1 = 1, T2 = 1
Tn+3 = Tn + Tn+1 + Tn+2
Then the start matrix is {1, 1, 0}, covering T2, T1, T0. Assign values from right to left because the leftmost value is the final answer to output, and the rightmost is the first value within the input range n.
But note:
If it’s Tn+4 = Tn + Tn+3
T0 = 0, T1 = 1, T2 = 1, T3 = 2
The start matrix is {2, 1, 1, 0}, covering T4, T3, T2, T1, the entire range on the right side of the equation. - The construction of the base matrix is also based on the relationships on the right side of the equation.
The first column of the matrix is the coefficients on the right side of the equation. For example, Tn+3 = Tn + Tn+1 + Tn+2, the first column is {1, 1, 1}.
If it’s Tn+4 = Tn + Tn+3
It can be viewed as: Tn+4 = 1 * Tn + 0 * Tn+1 + 0 * Tn+2 + 1 * Tn+3, so the first column of the base matrix is {1, 0, 0, 1}.
Other columns are calculated by setting unknowns:
For example: Tn+3 = Tn + Tn+1 + Tn+2, set the base matrix as: {1, a, d} {1, b, e} {1, c, f}
Then, by calculating backward and assigning values, we find the values of a, b, c, d, e, f. For instance, in the Tribonacci sequence example, we get: {1, 1, 0} {1, 0, 1} {1, 0, 0}How to Obtain the Final Result
Taking the Tribonacci sequence as an example, after multiplying the start array by the base matrix processed through fast exponentiation, the leftmost value is the required result. The reason it’s n - 2 instead of n - 1 or n is that the start array has 3 dimensions, but only the leftmost one is useful. 3 - 1 = 2, so it’s n - 2. Therefore, when n == 0 and n == 1, they are missed during the start evaluation, so they can be directly preprocessed and return 0 and 1, respectively.
Example Overview of kD 1-order Matrix Fast Exponentiation
Here, https://leetcode.cn/problems/count-vowels-permutation/ is used as an example:
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
class Solution {
public:
const int MOD = 1e9 + 7;
vector<vector<int>> multiply(vector<vector<int>> a, vector<vector<int>> b) {
int n = a.size();
int m = b[0].size();
int k = a[0].size();
vector<vector<int>> ans(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int c = 0; c < k; ++c) {
ans[i][j] = ((long long)a[i][c] * b[c][j] + ans[i][j]) % MOD;
}
}
}
return ans;
}
vector<vector<int>> power(vector<vector<int>> a, int p) {
int n = a.size();
vector<vector<int>> ans(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
ans[i][i] = 1;
}
while (p > 0) {
if ((p & 1) == 1) {
ans = multiply(ans, a);
}
p >>= 1;
a = multiply(a, a);
}
return ans;
}
int countVowelPermutation(int n) {
vector<vector<int>> start = { {1, 1, 1, 1, 1} }; // Each letter can be counted as one result at the end
vector<vector<int>> base = {
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 0}
};
vector<vector<int>> end = multiply(start, power(base, n - 1));
int ans = 0;
for (int e : end[0]) {
ans = (e + ans) % MOD;
}
return ans;
}
};
Its computational process is similar to 1D k-order matrix fast exponentiation, but its underlying logic differs. Below is an analysis of its underlying logic.
Underlying Logic Analysis of kD 1-order Matrix Fast Exponentiation
How to Determine It’s kD 1-order Matrix Fast Exponentiation
Its form must satisfy that each element follows a first-order formula like F(n) = F(n - 1), but there are multiple such first-order formulas simultaneously, each corresponding to one dimension. Finally, the results from all dimensions are summed.
How to Construct the start and base Matrices
- Construction of the start matrix
When the total number of elements is 1, it can be the corresponding element, so set that element to 1. In this problem, each element can be set to 1 when the total number of elements is 1, so start = {1, 1, 1, 1, 1}. - Construction of the base matrix
The horizontal coordinates can be each element, and the vertical coordinates are the previous elements corresponding to each element. The base can be viewed as:Values for n: a 0 1 0 0 0 e 1 0 1 0 0 i 1 1 0 1 1 o 0 0 1 0 1 u 1 0 0 0 0 Values for n-1: a e i o uIf a can be preceded by e, i, u, set the intersection of a with e, i, u to 1. The same logic applies to others.
How to Obtain the Final Result
After processing with matrix fast exponentiation, multiply the start matrix by the base matrix raised to the power of n - 1 (removing the known first instance), then sum the computed values from each dimension in the resulting matrix to obtain the final result.
FAQ
How to Obtain the Expression for 1D k-order Matrix
The expression F(n) = F(n - 1) + F(n - 2) + … + F(n - k) is the core for solving 1D k-order problems and should be given by the problem. However, some problems may not provide it. In such cases, brute-force methods or pattern-finding through tabulation can be used to solve it.
