快速幂

常规幂运算：

计算a^n 需要O(n)次乘法，例如2^5 = 2 * 2 * 2 * 2 * 2, so overwhelming
当n很大时这种方法不可取

快速幂：

可以在O(log(n))的时间复杂度内完成计算

基本思想：二分法

如果n是偶数：a^n = (a^(n/2)) ^ 2;
如果是奇数：a^n = (a^(n-1)) * a;

算法实现

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

#include<iostream>
using namespace std;
using ll=long long;

//迭代版
ll fast_pow(ll a,ll n){
    ll result=1;
    while(n>0){
        if(n&1){  //如果n是奇数
        result*=a;
        }
        a*=a;
        n>>=1;
    }
    return result;
}

//递归版
ll FastPow(ll a,ll n){
    if(n==0) return 1;
    if(n%2==0){
        ll half=FastPow(a,n/2);
        return half*half;
    }else{
        return a*FastPow(a,n-1);
    }
}

笔者觉得还是第二版更好理解，因为第一版还需要额外了解一点小知识点（课堂上必定会有提及，但是我摸鱼故没听见

迭代版补充：

  1. n&1为位运算，检查n是否为奇数,只检查 n 的二进制最后一位（二进制最后一位是1），如果指数是奇数，需要将当前的底数乘进结果中

  2. n>>1等价于n/=2,使用位右移一位，相当于整除以2

    1. 计算过程举例
      Q:计算3^13
      初始：result=1, a=3, n=13 (二进制为1101)

    第一轮：n=13(奇数)
    n&1=1 -> result= 1 * 3 =3
    a = 3 * 3 = 9
    n = 13>>1 =6

    第二轮： n=6(偶数)
    n&1=0 -> result不变
    a = 9 * 9 = 81
    n = 6>>1 = 3

    第三轮： n=3(奇数)
    n&1=1 -> result = 3 * 81 = 243
    a = 81 * 81 = 6561
    n = 3>>1 = 1

    第四轮： n=1(奇数)
    n&1=1 -> result =243 * 6561 = 1594323
    a = 6561 * 6561
    n= 1>>1 = 0;

    return 1594323

看完例子相信大家有种豁然开朗之感，就像英语背单词需要带入句子，如果不理解如何运行不妨举个例子试一试

带模运算的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//其实就是一步一除模
#include<iosteam>
using namespace std;
using ll = long long;

ll fast_mod(ll a,ll n,ll mod){
   ll result=1;
   a%=mod; //先取模防止a过大

   while(n>0){
       if(n&1){
       result=(result*a)%mod;
       }
       a=(a*a)%mod;
       n>>1;
   }
   return result;
}

上难度

我的目的终于达成，在讲完这么多前期准备工作过后,我们迎来终于要上场的问题

矩阵快速幂（以斐波那契数列为例

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
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

using Matrix= vector<vector<ll>>;

Matrix Mul(const Matrix& A,const Matrix& B,ll mod){

    int n=A.size();     //A的行数
    int m=B[0].size();  //B的列数
    int p=B.size();     //B的行数(A的列数)

    //创建结果矩阵C,大小为n*m,初始化为0
    Matrix C(n,vector<ll>(m,0));

    //三重循环
    for(int i=0;i<n;i++){  //C的每一行
        for(int j=0;j<m;j++){  //C的每一列
            for(int k=0;k<p;k++){   //累加A第i列和B第j列的点积（妙
            C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;

            }
        }
    }
    return C;
}

Matrix FastPow(Matrix base,ll n,ll mod){
    int size=base.size();  //获取矩阵的维度，假设是方阵

//创建结果方阵，初始化为单位矩阵
    Matrix result(size,vector<ll>(size,0));
    for(int i=0;i<size;i++){
        result[i][i]=1;
    }

    //核心循环：类似快速幂
    while(n>0){
        if(n&1){
            // result*=base
            result=Mul(result,base,mod);
        }
        //base*=base
        base=Mul(base,base,mod);

        n>>1;
    }
    return result;
}

ll fibo(ll n,ll mod){
    if(n<=1) return n;

    //核心：斐波那契的矩阵表示（妙啊
//| F(n+1) |   | 1 1 |   | F(n)   |
//|        | = |     | * |        |
//|  F(n)  |   | 1 0 |   | F(n-1) |
//    简化为
//| F(n+1) |   | 1 1 |^n   | F(1) |
//|        | = |     |   * |      |
//|  F(n)  |   | 1 0 |     | F(0) |
//通过矩阵联系起来了递归！！！
    Matrix base={{1,1},{1,0}};

    Matrix result=FastPow(base,n-1,mod);

    return result[0][0];
}

快速幂这种基础算法，是构建更复杂算法（矩阵快速幂、数论运算）的基石。基础不牢，地动山摇。线代也要好好学，嗯。