快速幂
当求某一正整数 a a a 的 n n n 次幂 a n a^n an 时，常用的做法是将 a a a 连续乘以 n n n 次，其时间复杂度为 O ( n ) O(n) O(n) 。 事实上，该问题有时间复杂度为 O ( l o g n ) O(logn) O(logn) 的解法。其核心思想是： a n = { a n / 2 ∗ a n / 2 , n 为偶数 a n / 2 ∗ a n / 2 ∗ a , i n 为奇数 a^n= begin{cases} a^{n/2},*,a^{n/2}, & text {$n$ 为偶数} \ a^{n/2},*,a^{n/2},*a, & text{i$n$ 为奇数} end{cases} an={an/2∗an/2,an/2∗an/2∗a,n 为偶数in 为奇数
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/** * 求 a 的 n 次幂 * @param a * @param n * @return */ long pow(int a, int n) { long res = 1; while(n != 0) { if(n % 2 == 1) { res *= a; } n /= 2; a *= a; } 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/** * 矩阵 a 的 n 次幂 * @param a * @param n * @return */ int[][] pow(int[][] a, int n) { int k = a.length; int[][] res = new int[k][k]; for(int i = 0; i < k; i++) { res[i][i] = 1; } while(n != 0) { if(n % 2 == 1) { res = mul(res, a); } n /= 2; a = mul(a, a); } return res; } /** * 矩阵乘法 * @param a * @param b * @return */ int[][] mul(int[][] a, int[][] b) { int a_row = a.length; int b_col = b[0].length; int n = a[0].length; //a的列数等于b的行数 int[][] res = new int[a_row][b_col]; for(int i = 0; i < a_row; i++) { for(int j = 0; j < b_col; j++) { for(int k = 0; k < n; k++) { res[i][j] += a[i][k] * b[k][j]; } } } return res; }
线性dp优化
一组 D P DP DP 状态，其实等价于一个向量。而DP状态的转移方程，可以是对一个向量做变形的矩阵。那么本质上从一个向量到另一个状态的向量，是可以通过一个矩阵来做到。矩阵具有结合律，我们可以先对右半部分矩阵用快速幂得到一个终极的变形矩阵，再乘以向量，就可以把 O ( n ) O(n) O(n) 的计算优化到 O ( l o g ( n ) ) O (log (n)) O(log(n))。 （转自简书——DP的五类优化-快速幂，四边形不等式）
例题：
1、 F i b o n a c c i Fibonacci Fibonacci 数列
递推式： F n = F n − 1 + F n − 2 , ( n > 2 ) F_n=F_{n-1}+F_{n-2},;(n > 2) Fn=Fn−1+Fn−2,(n>2)
d p dp dp 状态转移方程： d p [ n ] = d p [ n − 1 ] + d p [ n − 2 ] , ( n > 2 ) dp[n] = dp[n-1] +dp[n-2],;(n>2) dp[n]=dp[n−1]+dp[n−2],(n>2)
由
F
i
b
o
n
a
c
c
i
Fibonacci
Fibonacci 数列的递推式可以得到如下矩阵关系式：
(
F
n
F
n
−
1
)
=
(
1
1
1
0
)
(
F
n
−
1
F
n
−
2
)
=
(
1
1
1
0
)
n
−
2
(
F
2
F
1
)
begin{pmatrix} F_n \ F_{n-1} end{pmatrix} = begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix} begin{pmatrix} F_{n-1} \ F_{n-2} end{pmatrix} = begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix}^{n-2} begin{pmatrix} F_2 \ F_1 end{pmatrix}
(FnFn−1)=(1110)(Fn−1Fn−2)=(1110)n−2(F2F1)
故该问题转换成矩阵的
n
n
n 次幂，实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/** * 求f(n) * @param n * @return */ int fibonacci(int n) { if(n == 0) { return 0; } if(n <= 2) { return 1; } int[][] initial = {{1}, {1}}; //f(2), f(1) int[][] transition = {{1, 1}, {1, 0}}; //转换矩阵 int[][] result = new int[2][2]; //结果矩阵 f(n), f(n-1) result = mul(pow(transition, n - 2), initial); return result[0][0]; }
注： m u l mul mul 函数和 p o w pow pow 函数均为矩阵快速幂部分中的对应函数
现在有一个问题——如何得到转换矩阵？
未想到通解。。。
2、CCF202006第四题 1246 ( d i g i t s ) 1246(digits) 1246(digits)
后续更新。。。
最后
以上就是慈祥高跟鞋最近收集整理的关于快速幂-矩阵快速幂-线性dp优化的全部内容，更多相关快速幂-矩阵快速幂-线性dp优化内容请搜索靠谱客的其他文章。
![[矩阵快速幂 优化DP] 51Nod 1311 转换机](/uploads/reation/bcimg1.png)
![[week14] D - Q老师染砖（选做） —— 矩阵快速幂优化DP题意分析总结代码](/uploads/reation/bcimg6.png)
发表评论 取消回复