首页 > 其他分享 >矩阵快速幂

矩阵快速幂

时间:2023-02-26 12:23:06浏览次数:28  
标签:matrix int 矩阵 long m1 include 快速

求矩阵的 k 次幂

 

#include <iostream>
 #include <cmath>
 #include <algorithm>
 using namespace std; 
 #define N 100
 const int mod =1e9+7;
 
 
 #define int long long
  struct matrix {
  	int a[N+2][N+2];
  };
  matrix m1; 
  int n;
  
  void init_(matrix &x){
  	
  	int i,j;
  	for(i=1;i<=n;i++)
  	 for(j=1;j<=n;j++) {
  	 	 x.a[i][j]=0;
  	 	 if(i==j) x.a[i][j]=1;
  	 }
  }
  matrix mul(matrix &x,matrix &y){
 	int i,j,k;
 	matrix z;
 	
 	for(i=1;i<=n;i++)
 	 for(j=1;j<=n;j++){
 	 	z.a[i][j]=0;
 	 	for(k=1;k<=n;k++)
 	 	 z.a[i][j]+=x.a[i][k]*y.a[k][j], z.a[i][j]%=mod;
 	 }
 	
 	return z;
 }
   matrix ksm(matrix &x,int k){
 	matrix tmp=x, ans;
 	init_(ans);
 	
 	while(k){
 		if(k&1) ans=mul(ans,tmp);
 		
 		tmp=mul(tmp,tmp); 
 		k/=2;
 	}
 	return ans;
 }
 
  signed main(){
 	std::ios::sync_with_stdio(0);
 	int m;
 	cin>>n>>m;
 	for(int i=1;i<=n;i++) 
 	 for(int j=1;j<=n;j++)cin>>m1.a[i][j];
 	matrix t= ksm(m1,m);
 	for(int i=1;i<=n;cout<<endl,i++)
 	 for(int j=1;j<=n;j++)
 	  cout<<t.a[i][j]%mod<<' ';
 }
 
 

 

标签:matrix,int,矩阵,long,m1,include,快速
From: https://www.cnblogs.com/towboa/p/17156444.html

相关文章

  • 搜索二维矩阵---二分查找
    搜索二维矩阵编写一个高效的算法来判断 mxn 矩阵中,是否存在一个目标值。该矩阵具有如下特性:每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一......
  • 龟速乘&快速乘&快速幂&压位高精快速幂 模板
    龟速乘#defineintlonglonginlineintmul_slow(intx,inty,intmod){ intres=0; while(y){ if(y&1)res=(res+x)%mod; x=(x+x)%mod; y>>=1; } returnres......
  • QT多线程实现冒泡排序和快速排序方法一
    qt4的线程方式#include"mythread.h"#include<QElapsedTimer>#include<QDebug>Generate::Generate(QObject*parent):QThread(parent){}voidGenerate::recvNum(intnum......
  • qt多线程实现快速排序和冒泡排序方法二
    qt5多线程处理方式#include"mainwindow.h"#include"ui_mainwindow.h"#include"mythread.h"#include<QThread>MainWindow::MainWindow(QWidget*parent):QMainWindo......
  • 快速排序
    classQuickSort{intpartition(int[]a,intlow,inthigh){intpivot=a[low];//第一个元素作为枢轴while(low<high){//用low、high搜索......
  • [专题总结]Gridea快速免费搭建个人博客
    介绍或许你很想把你所知道的问题写出来,或许你文思泉涌,想给大家分享。我相信,你一定能写好博客,只要坚持,就可以了。或许大家会不理解,为什么不用大平台的博客呢?或许你稍微了......
  • 持久化_AOF 与Jedis_快速入门
    持久化_AOF1.AOF:日志记录的方式,可以记录每一条命令的操作。可以每一次命令操作后,持久化数据 1.编辑redis.windwos.conf文件 ......
  • Java负载均衡简介及快速入门并实战(有源码)
    Java负载均衡是什么?将负载(工作任务,访问请求)进行分摊到多个操作单元(服务器,组件)上执行服务端:服务提供端,比如nginx负载均衡客户端:服务请求方,在发送请求之前已经选好了由哪个......
  • 798. 差分矩阵
    二维差分模板题https://www.acwing.com/problem/content/800/同一维差分一样的思想,重要的也是时刻保证a[i]=b[0]+b[1]+...+b[i]在二维则是:a[i][j]=b[0][0]+b[0][1]+...b[......
  • Pytorch快速使用手册 02张量操作
    importosimporttqdmimporttorchimportrandomimportshutilimportnumpyasnp2TenosrOperation2.1Baseinformationoftensortensor=torch.rand([2,5]......