【模板】快速幂 && 矩阵快速幂

朴素快速幂

 

快速幂思想优化点:
由于计算机二进制数的位运算效率高, 我们将指数用二进制数表示
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各部分各个计算, 再相乘 -> 结合律。
所以某种类型的变量的一种运算(整数加法，整数乘法，矩阵乘法)满足结合律，则该变量自身(幂运算(自身相乘), 数乘运算(自身相加))的这种运算，可以被快速幂思想优化。

 

【模板】快速幂

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
int b, p;
LL k;

int qmi(int a, int b, LL p)
{
    int ans = 1 % p; //如果没有这行，hack数据: 1 0 1，应该输出0，但是输出1
    while(b)
    {
        if(b & 1) ans = (LL)ans * a % p;
        b >>= 1;
        a = (LL)a * a % p; 
    }
    return ans;
}

int main()
{
    cin >> b >> p >> k;
    printf("%d^%d mod %lld=%d
", b, p, k, qmi(b, p, k)); //因为k是LL类型，所以输出必须要用%lld否则会输出0

}

 快速乘优化的快速幂

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>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 110, mod = 1e9 + 7;
typedef long long LL;

int n;

struct mat{
    LL m[N][N];
}unit;

mat operator * (const mat &x, const mat &y)
{
    mat ans;
    LL t;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
        {
            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;
}

void mat_qmi(mat a, LL k)
{
    mat res = unit;
    
    while(k)
    {
        if(k & 1) res = 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;
}