一、快速幂 $$a^b$$

1、原理：
当b是$$2^k, \ \ a^b=a^{2^k}= ((a^2)^2)^2\cdots $$
b可以转化为二进制 $$b = 2^{k_0} +2^{k_1}+2^{k_2}+2^{k_3}\cdots$$
如：$$13=0b1101=2^3+2^2+2^0$$
$$a^b=a^{2^{k_0} +2^{k_1}+2^{k_2}+2^{k_3}\cdots}=a^{2^{k_0}}\times a^{2^{k_1}}\times a^{2^{k_2}}\times \cdots$$
如：$$a^{13} = a^{2^0}\times a^{2^2}\times a^{2^3}$$
2、算法
a迭代计算平方，即a = a * a.
得到序列:$$a=\{ a^{2^{0}}, a^{2^{1}},a^{2^{2}},a^{2^{3}},\cdots \}$$ .
针对二进制的b某一位若是1，则计算结果re乘以a.
如： $$3^{13},a=3,b=13=0b1101$$

3、代码

def power(base,exponent):
    res = 1
    while exponent:
        if exponent & 1:  # 判断当前的最后一位是否为1，如果为1的话，就需要把之前的幂乘到结果中。
            res *= base
        base *= base  # 一直累乘，如果最后一位不是1的话，就不用了把这个值乘到结果中，但是还是要乘。
        exponent = exponent >> 1
    return res

typedef long long ll;
ll qpow(ll a, ll b)//计算a^b
{
    ll re = 1;
    while(b)
    {
        if(b & 1)//判断n的最后一位是否为1
            re = (re * a);
        b >>= 1;//舍去b的最后一位
        a = (a * a) ;//将a平方
    }
    return re;
}

二、快速幂取模 $$a^b\ mod\ c $$

1、模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）

这里可以用到第3条
2、代码

typedef long long ll;
ll mod;
ll qpow(ll a, ll n)//计算a^n % mod
{
    ll re = 1;
    while(n)
    {
        if(n & 1)//判断n的最后一位是否为1
            re = (re * a) % mod;
        n >>= 1;//舍去n的最后一位
        a = (a * a) % mod;//将a平方
    }
    return re % mod;
}

三、矩阵快速幂

1、斐波那契数列问题矩阵
对于$$i\geq 3,F_i=F_{i-1}+F_{i-2}$$
矩阵递推公式：
$$ \left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right) \times \left( \begin{matrix} F_{i-1} \\ F_{i-2} \end{matrix} \right) = \left( \begin{matrix} F_{i} \\ F_{i-1} \end{matrix} \right) $$
矩阵通项公式：
$$\left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right) ^{n-2} \left( \begin{matrix} 1 \\ 1 \end{matrix} \right) = \left( \begin{matrix} F_{i} \\ F_{i-1} \end{matrix} \right) $$
2、代码

const ll mod = 10000;
const int maxv = 2;

struct Matrix {
    ll a[maxv][maxv]; //矩阵

    Matrix operator*(const Matrix &b) const& { 
        //矩阵乘法，复杂度O(maxv^3)，也可看作常数，但maxv较大（大于5）时会使运算时间提高好几个数量级
        Matrix ans;
        for (int i = 0; i < maxv; ++i) {
            for (int j = 0; j < maxv; ++j) {
                ans.a[i][j] = 0;
                for (int k = 0; k < maxv; ++k) {
                    ans.a[i][j] += a[i][k] * b.a[k][j] % mod;
                    ans.a[i][j] %= mod;
                }
            }
        }
        return ans;
    }
    static Matrix qpow(Matrix x, ll n) {//矩阵快速幂，将乘法复杂度看作常数则复杂度为O(log n)
        Matrix ans;
        for (int i = 0; i < maxv; ++i) {
            for (int j = 0; j < maxv; ++j) {
                if (i == j)
                    ans.a[i][j] = 1;
                else
                    ans.a[i][j] = 0;
            }
        }//初始化为单位矩阵，参考普通数字的快速幂这里初始化为1
        while (n) {//其余细节基本相同
            if (n & 1)
                ans = ans * x;
            x = x * x;
            n >>= 1;
        }
        return ans;
    }
    Matrix(ll temp[maxv][maxv]) {//构造方法
        for (int i = 0; i < maxv; ++i) {
            for (int j = 0; j < maxv; ++j) {
                a[i][j] = temp[i][j];
            }
        }
    }
    Matrix() { }
};

ll fib(ll n) {//求取斐波那契数列第n项（本题取模）
    if (n == 0)
        return 0;
    if (n <= 2)
        return 1;
    
    ll temp[maxv][maxv] = {
        1, 1,
        1, 0
    };
    Matrix m(temp);
    m = Matrix::qpow(m, n - 2);
    return (m.a[0][1] + m.a[0][0]) % mod;
}

3、矩阵快速幂其他应用

四、参考网站

https://www.cnblogs.com/sun-of-Ice/p/9330352.html
https://blog.csdn.net/zgzczzw/article/details/52712980

• dx版本、openGL、Vulkan与游戏
• vc++小贴士
• MinHook--CCKa_max 的Directx-11-example(64)
• c++ hookd3d imgui 一步步操作（艾鱼）
• mediapipe win10 编译、运行命令说明

发表新评论 取消回复

发送