当前位置：首页 > article >正文

方阵幂次(矩阵快速幂）

article 2025/4/1 3:59:51

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> fuc(vector<vector<int>> a,vector<vector<int>> b){ // 矩阵乘法函数
  vector<vector<int>> f(n,vector<int>(n));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      for(int k=0;k<n;k++){
        f[i][j]+=a[i][k]*b[k][j];
      }
    }
  }
  return f;
}

int main()
{
  int m;cin>>n>>m;
  vector<vector<int>> a(n,vector<int>(n));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }

  vector<vector<int>> ans(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
        ans[i][i] = 1;  // 单位矩阵
    }
  while(m){ // 快速幂算法
    if(m&1) ans=fuc(ans,a);
    a=fuc(a,a);
    m>>=1;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

矩阵乘法函数 fuc 用vector可以作为矩阵返回值

ans 要初始化为一个单位矩阵

然后用快速幂计算结果

查看全文

http://www.kler.cn/a/613403.html