光与影的个人博客

NEUCoder

0%

快速幂整理

发表于 更新于 分类于 ，

1 什么是快速幂

在求幂次操作时，一般采用逐个相乘的方式，求多少阶幂次，就需要进行多少次乘法，乘法的时间复杂度为O(N)，通过引入”备忘录“和二分思想，将乘法次数从 降低到

主要思想：

  1. 求 N幂次问题 转化为 求两个 N/2幂次的乘积
  2. 两个相同的 N/2幂次子问题，只需要求解一次

    1.1 递归伪代码：

  • 递归实现较为简洁，但是会存在递归栈占用，递归树深度为
1
2
3
4
5
6
7
8
9
10
11
12
int getPow(int x,int e){
    if(e == 0){
		return 1;
    }
    //计算子问题
    int temp = getPow(x, e / 2);
    int result = temp * temp;
    if(e % 2 != 0){
        result *= x;
    }
    return result;
}

1.2 迭代伪代码：

观察递归代码，可以得到递归过程类似于将指数e转化为二进制的过程

  • 在底数转化二进制的某位为1时，对应递归子问题为奇数时乘以底数，
1
2
3
if(e % 2 != 0){
    result *= x;
}
  • 在递归返回时，每向上返回一层 该位置乘的底数，都要平方一次
1
int result = temp * temp;

根据以上分析可得递归代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
int getPow(int x,int e){
	int result = 1;
	while(e > 0){
		if(e % 2 != 0){
			result *= x;
		}
        //阶数向右移动
        x *= x;
        //等价于从底向上递归
		e >>= 1;
	}
	return result;
}

1.3 添加了避免越界的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
int getPow(int x,int e){
	int result = 1;
	while(e > 0){
		if(e % 2 != 0){
			result = result * x mod number;
		}
        //阶数向右移动
        x = x * x mod number;
        //等价于从底向上递归
		e >>= 1;
	}
	return result;
}

1.4 快速幂扩展

快速幂思路不止可以应用在整数乘积上，同样可扩展到类似的矩阵乘积

2 典型例题

2.1 洛谷 P3390 【模板】矩阵快速幂

难点在于避免越界和矩阵乘法

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
  static int MOD_NUMBER = 100000007;
  public static long[][] matMul(long[][] mat1, long[][] mat2){
      if(mat1 == null){
          return mat2;
      }
      //乘积结果存储在result中
      long[][] result = new long[mat1.length][mat1.length];
      long temp;
      for(int i = 0;i < mat1.length;i++){
          for(int j = 0;j < mat1.length;j++){
              temp = 0;
              //第i行与第j列相乘
              for(int m = 0; m < mat1.length;m++){
                  //避免越界的关键点
                  temp  = (temp + mat1[i][m] * mat2[m][j] % MOD_NUMBER) % MOD_NUMBER;
              }
              result[i][j] = temp;
          }
      }
      return result;
  }
  public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      int n = scanner.nextInt();
      Long k = scanner.nextLong();
      long[][] aimMatrix = new long[n][n];
      //读取matrix数组
      for(int i = 0;i < n;i++){
          for(int j = 0;j < n;j++){
              aimMatrix[i][j] = scanner.nextLong();
          }
      }

      long[][] result = null;
      while(k > 0) {
          if (k % 2 != 0) {
              result = matMul(result, aimMatrix);
          }
          k >>= 1;
          aimMatrix = matMul(aimMatrix, aimMatrix);
      }
      //输出结果集合,省略
System.....
  }

2.2 力扣 1922. 统计好数字的数目

难点在于将题目转化为求幂形式，通过归纳得到数组位数每增加两位，好数字数目*20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countGoodNumbers(long n) {
        //设置初始化值
        long result = 1;
        if(n % 2 == 1){
            result = 5;
        }
        n = n / 2;
        long a = 20;
        //快速幂模板
        while(n > 0){
            if(n % 2 == 1){
                result = result * a % 1000000007;
            }
            //右移一位
            n >>= 1;
            a = a * a % 1000000007;
        }
        return (int)result;
    }
}