矩阵快速幂+整数快速幂

缺乏、安全感 2022-05-11 13:22 260阅读 0赞

嗯~ 今天总结一下快速幂的知识点

### 1.首先讲一下矩阵相乘 ###

矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\*p的矩阵，那么B矩阵必定是p\*n的矩阵，最后A\*B得到的矩阵C是m\*n的矩阵。

其中矩阵C的第 i 行第 j 列元素![C\_\{ij\}][C_ij]是矩阵A的第 i 行元素![a\_\{i1\},a\_\{i2\},...,a\_\{ip\}][a_i1_a_i2_..._a_ip]与矩阵B的第j列相应元素![b\_\{1j\},b\_\{2j\},...,b\_\{pj\}][b_1j_b_2j_..._b_pj]的乘积之和。

![8ad4b31c8701a18bd6fe9b5e992f07082838fe8e.jpg][]

举个栗子，如下所示：

![adaf2edda3cc7cd955ae9be73e01213fb80e9109.jpg][]

### 2.整数快速幂 ###

为了引出快速幂的好处，我们根据下面的栗子来认识一下快速幂算法的优化之处。

例如我们要求x^8，暴力的方法就是用x乘7次，但是如果我们这样算：（x\*x）（x\*x）（x\*x）（x\*x）， 那我们就只用算出x\*x，然后用x\*x乘3次就可以得到结果，这样总共就乘了4次，所以我们就引入快速幂的算法。

由![x^\{m\}\\times x^\{n\}=x^\{m+n\}][x_m_times x_n_x_m_n]我们引进了2进制的知识。

由于如果幂太小的话，就体现不出快速幂算法的优化了，所以这里我们用x^21做栗子，

![x^\{21\}=x^\{16\}\\times x^\{4\}\\times x^\{1\}][x_21_x_16_times x_4_times x_1]，（21的二进制是10101）。

由上面可以看出二进制位中如果是1的话就乘，如果是0的话就不用乘，

下面是用整数快速幂求（ x^n）%k 的核心代码：

int QuickPow(int x,int n,int k)
    {
        int ans = 1;
        while(n)
        {
            if(n&1)///&运算，如果k的二进制中最后一位是1的话结果就是1，如果是0的话结果就是0
                ans = (ans * x) % k;
            x = (x * x) % k;
            n = n >> 1;///k的二进制数右移一位
        }
        return ans;
    }

（补充一下&运算的知识）如下图.

![70][]

### 3.矩阵快速幂 ###

有了整数快速幂的基础之后，矩阵快速幂就简单多了。

下面是用矩阵快速幂求n\*n的矩阵S^k的核心代码：

///矩阵类结构体
    struct matrix
    {
        int m[20][20];
    }S;
    matrix matrix_multiply(matrix A,matrix B)///求矩阵的乘积
    {
        matrix C;
        for(int i = 1; i <= n; i++)///初始化为0矩阵
        {
            for(int j = 1; j <= n; j++)
                C.m[i][j] = 0;
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k <= n; k++)
                    C.m[i][j] = (C.m[i][j] +A.m[i][k]*B.m[k][j]) % Mod;
            }
        }
        return C;
    }
    matrix QuickPow(int k)
    {
        matrix ans;///ans初始化为单位矩阵
        for(int i = 1; i <= n; i++)///单位矩阵乘任何矩阵都等于矩阵本身
        {
            for(int j = 1; j <= n; j++)
                ans.m[i][j] = 0;
            ans.m[i][i] = 1;
        }
        while(k)
        {
            if(k&1)
                ans = matrix_multiply(ans,S);
            S = matrix_multiply(S,S);
            k = k >> 1;
        }
        return ans;
    }

[C_ij]: https://private.codecogs.com/gif.latex?C_%7Bij%7D
[a_i1_a_i2_..._a_ip]: https://private.codecogs.com/gif.latex?a_%7Bi1%7D%2Ca_%7Bi2%7D%2C...%2Ca_%7Bip%7D
[b_1j_b_2j_..._b_pj]: https://private.codecogs.com/gif.latex?b_%7B1j%7D%2Cb_%7B2j%7D%2C...%2Cb_%7Bpj%7D
[8ad4b31c8701a18bd6fe9b5e992f07082838fe8e.jpg]: https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D334/sign=5e0cfe86de33c895a27e9e78e5137397/8ad4b31c8701a18bd6fe9b5e992f07082838fe8e.jpg
[adaf2edda3cc7cd955ae9be73e01213fb80e9109.jpg]: https://gss0.bdstatic.com/94o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D594/sign=01474d246759252da7171d0d009a032c/adaf2edda3cc7cd955ae9be73e01213fb80e9109.jpg
[x_m_times x_n_x_m_n]: https://private.codecogs.com/gif.latex?x%5E%7Bm%7D%5Ctimes%20x%5E%7Bn%7D%3Dx%5E%7Bm&plus;n%7D
[x_21_x_16_times x_4_times x_1]: https://private.codecogs.com/gif.latex?x%5E%7B21%7D%3Dx%5E%7B16%7D%5Ctimes%20x%5E%7B4%7D%5Ctimes%20x%5E%7B1%7D
[70]: /images/20220505/5da702b37c31426d8120035151f3906a.png