快速幂
递归求解
快速幂实际是分治的思想，把大的次幂一步步除以二。例如求解x17，幂向下「递」的过程为：17->8->4->2->1，1即x本身，向上「归」即可得到结果。代码如下：
1
2
3
4
5
6
7
8
| public double pow(double x, long p){
if(p == 0) return 1;
if(p == 1) return x;
double sub = pow(x, p/2);
double ret = sub * sub;
if(p % 2 == 1) ret *= x;
return ret;
}
|
迭代求解
1
2
3
4
| 举例x^77，77的二进制数每一位都有相应的权值
1 0 0 1 1 0 1
x^64 x^32 x^16 x^8 x^4 x^2 x^1
最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77
|
可以通过上面的例子直观理解，其实就是把幂次转换为二进制，从低位开始遍历，同时维护xp，其中p为2的幂，如果某个二进制位为1，将其对应的xp累乘到结果。代码如下：
1
2
3
4
5
6
7
8
9
| public long pow(long x, int p){
long ret = 1;
while(p > 0){
if(p % 2 == 1) ret = ret * x % MOD;
x = x * x % MOD;
p >>= 1;
}
return ret;
}
|
这里涉及到了另一个小知识点为快速幂取模，分治运算时顺便取下模就好了。
由于本质是把幂次转换为二进制，快速幂的时间复杂度为O(logn)。
矩阵快速幂
在求解某个矩阵mat的幂时同样可以采用快速幂，因为矩阵乘法与数值乘法有类似的幂次分解性质。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public long[][] pow(long[][] mat, int n){
long[][] ret = {{1, 0, 0, 0, 0, 0}};
while(n > 0){
if(n % 2 == 1) ret = multiply(ret, mat);
mat = multiply(mat, mat);
n /= 2;
}
return ret;
}
public long[][] multiply(long[][] a, long[][] b){
int m1 = a.length, n1 = a[0].length;
int m2 = b.length, n2 = b[1].length;
long[][] c = new long[m1][n2];
for(int i = 0;i < m1;++i){
for(int j = 0;j < n2;++j){
for(int k = 0;k < n1;++k){
c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
}
}
}
return c;
}
|
题目
50. Pow(x, n) - 力扣（LeetCode） 快速幂模板题
372. 超级次方 - 力扣（LeetCode） 快速幂取模
552. 学生出勤记录 II - 力扣（LeetCode） 用到了矩阵快速幂，但关键是得到需要幂运算的矩阵
__END__
