快速幂&矩阵快速幂

---

快速幂

模板题链接

特点

• 对于普通的求（整数次）幂运算，如求$a^b$，需要将$a$连乘$b$次，复杂度为$O(b)$
• 使用快速幂能使得复杂度降为$O(logb)$，大大优化了计算时间

原理

为方便理解，这里直接给出实例：

求整数次幂时，比如：$3^{11}$，首先我们将指数$11$写成二进制形式$1011$，那么计算式就可以写成$3^{(1011)_2}$，再将其拆开写成

$$3^{(1011)_2}=3^8*3^0*3^2*3^1=3^{1*2^3}*3^{0*2^2}*3^{1*2^1}3^{1*2^0}$$

为什么要写成这样的形式呢？

我们发现，从右往左看上面的计算式，最右边是$3^1$，将它自乘一次，就会得到$3^2$，将$3^2$自乘一次得到$3^4$，然后得到$3^8$，是不是发现规律了？

没错，在指数的二进制表示法中，从低位向高位遍历，遇到$1$则自乘一次，再乘以答案（更新答案），遇到$0$也自乘一次，但不更新答案，即可在$O(logb)$的复杂度内完成幂运算。

代码

inline qpow(int x,int y){ //计算x^y
  int base=x,ans=1;
    while(y>0){
    if(y&1){ //如果y这一位为1，则需要更新答案
      ans*=base; //更新答案
            ans%=mod;
        }
        base*=base; //无论如何都需要自乘
        base%=mod;
        y>>=1; //y右移
    }
    return ans;
}

矩阵快速幂

模板题链接

原理

矩阵乘法 + 快速幂

完

• 实现过程只需要造一个结构体，里面存矩阵，然后重载一下乘法运算即可
• 重载矩阵乘法是三重循环（超级慢）

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct M{ //矩阵结构体
  ll mat[105][105];
}a;
ll n,k;
M operator*(M x1,M x2){ //重载乘法
  M res;
  memset(res.mat,0,sizeof(res.mat));
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=n;k++){
        res.mat[i][j]+=(x1.mat[i][k]*x2.mat[k][j])%mod;
        res.mat[i][j]%=mod; //多模多模很重要
      }
    }
  }
  return res;
}

inline M qpow(M x,ll y){ //快速幂
  M base=x,ans;
  for(int i=1;i<=n;i++){ //构造一个单位阵（相当于快速幂里面的ans=1）
    for(int j=1;j<=n;j++){
      if(i==j) ans.mat[i][j]=1;
      else ans.mat[i][j]=0;
    }
  }
  while(y>0){ //下面不解释了
    if(y&1) ans=ans*base; //有的题目需要注意左乘右乘
    base=base*base;
    y>>=1;
  }
  return ans;
}

int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>a.mat[i][j];
    }
  }
  M ans=qpow(a,k);
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cout<<ans.mat[i][j]%mod<<" "; //输出也要多模
    }
    cout<<endl;
  }
  return 0;
}