朴素快速幂

快速幂思想优化点:
由于计算机二进制数的位运算效率高, 我们将指数用二进制数表示
eg. 3^15 = 3^(1111)
3^15 = 3 * 3 * … * 3;
3^(1111) = 3^(2^3) * 3^(2^2) * 3(2^1) * 3(2^0);
3 2 1 0
(快速幂基本语句执行次数为4次，朴素算法基本语句执行次数为15次)

将15个3相乘, 分成4各部分各个计算, 再相乘 -> 结合律。
所以某种类型的变量的一种运算(整数加法，整数乘法，矩阵乘法)满足结合律，则该变量自身(幂运算(自身相乘), 数乘运算(自身相加))的这种运算，可以被快速幂思想优化。

ll qmi (int a, int b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a;
        /*
        两数相乘 = 指数 * 2(倍增) = 二进制进位
        3^2 * 3^2 = 3^(2 + 2) = 3^(10) -> 3^(100)
        */
        a = a * a;
        b >>= 1;
    }

    return res;
}

快速乘优化的快速幂

ll qmul (int a, int b)
{
    ll res = 0;
    while(b)
    {
        if(b & 1) res += a;
        a += a;
        b >>= 1;
    }

    return res;
}
ll qmi ()
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = qmul(res, a);
        a = qmul(a, a);
        b >>= 1;
    }

    return res;
}

广义快速幂

矩阵(matrix)乘法　－> 左行右列

1. 矩阵乘法可以用来优化很多的dp, 递推问题　斐波那契
   2. 矩阵的幂运算用快速幂思想优化就是我们所说的矩阵快速幂
   点我

矩阵快速幂

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 110, mod = 1e9 + 7;

int n;

struct mat
{
    ll m[N][N]; // c++ 中函数的返回值不能为数组，但是vector可以
}unit;

mat operator * (const mat &x, const mat &y)
{
    mat ans; // 因为此处的ans数组没有初始化为零,所以不能用它去加****
    ll t;
    for(int i = 0 ; i < n ; i ++ ) // 枚举a矩阵的行(左行)
        for(int j = 0 ; j < n ; j ++ ) // 枚举b矩阵的列(右列)
        {
            t = 0;
            for(int k = 0 ; k < n ; k ++ )
                t += x.m[i][k] * y.m[k][j] % mod;
            ans.m[i][j] = t % mod;
        }
    return ans;
}

void init_unit () // 初始化零元(单位矩阵)
{
    for(int i = 0 ; i < n ; i ++ ) unit.m[i][i] = 1;
}

mat mat_qmi (mat a, ll k)
{
    mat res = unit;　// 在广义快速幂中res为该运算的零元

    while(k)
    {
        if(k & 1) res = res * a; // 记住这里千万不能缩写成res *= a;
        a = a * a;
        k >>= 1;
    }

    return res;
}

int main ()
{
    ll k;   
    cin >> n >> k;
    init_unit();
    mat a;
    for(int i = 0 ; i < n ; i ++ )
        for(int j = 0 ; j < n ; j ++ )
            cin >> a.m[i][j];

    a = mat_qmi(a, k);

    for(int i = 0 ; i < n ; i ++ )
        for(int j = 0 ; j < n ; j ++ )
            if(j == n - 1) cout << a.m[i][j] << endl;
            else cout << a.m[i][j] << ' ';

    return 0;
}

矩阵快速幂求递推

斐波那契数列

swpu acm讲解
swpu 练习题1
swpu 练习题2

待更新…