快速幂与矩阵快速幂

69 阅读 0 评论 46 点赞

我是靠谱客的博主受伤大船，最近开发中收集的这篇文章主要介绍快速幂与矩阵快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速幂，顾名思义要快速解决数幂问题朴素算法中时间复杂度为O（n），在处理大数幂时显然会爆，这时要使用到快速幂的思想。

对于一个数的6方A^6们通常使用A*A*A*A*A*A，此时计算机进行5乘法运算，但我们可以将其拆分为(A*A)*(A*A)*(A*A)，这样做的优点在于当我们进行一次A*A运算后，只需将其乘3次即可得到结果，相比于原来的5次节约时间，在幂数更大一些时效果更佳明显。

那么问题来了，对于一个简单的幂运算我们可以快速找出我们需要的那个基数幂，即上文的A*A，在幂更大时该如何找到我们需要的基数呢。这时在将大数离散化之后，会发生一些变化，例如

A^156 将156呈2进制展开为 10011100

每一位1所代表的数位分别为 4 8 16 128 相加结果为156 那么我们可以得到

A^4*A^8*A^16*A^128=A^156 这样我们就找到了需要的基数 A^4

于是可以从二进制右端计算到左端，

while(n)
{
    if(n&1)
        ans=ans*A;
    n>>=1;
    A=A*a;
}

将矩阵带入后便可以解决一些大面积递推问题。例如大位菲波那切数列问题。

现需要菲数列第1亿项模10^6,递推当然可以解决但是，电脑：我选择死亡∠( ᐛ 」∠)＿。

f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) 当我们用矩阵表示时会得到

所以当我们需要更多位菲数列时，对中间的（1110）矩阵乘幂便得到了

后在使用快速幂思想简化中间矩阵，便解决了矩阵快速幂问题，矩阵快速幂就是把快速幂中的运算方式换成矩阵运算，线性代数中有详细介绍，直接附上模板

#include<bits/stdc++.h>
using namespace std;
const int N=4;
int n;
struct xx
{
    int a[N][N];
    
};ori,res;
xx mul(xx x,xx y)
{
    xx temp;
    memset(temp.a,0,sizeof(temp,a));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                temo.a[i][j]+=x.a[i][k]*y.a[k][j];
            }
        }
    }
    return temp;
}
void init()
{
    int x;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            scanf("%d",&x);
            ori.a[i][j]=x;
        }
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            res.a[i][j]=i==j?1:0;
        }
    }
}
xx calc(long long k)
{
    while(k)
    {
        if(k&2==1)
        {
            res=mul(ori,res);
            k-=1;
        }
        else
        {
            ori=mul(ori,ori);
            k/=2;
        }
    }
    return res.a[0][0];
}
int main()
{
    while(cin>>n)
    {
        init();
        calc(n);
    }
}