经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
算法初探 - 快速幂
来源:cnblogs  作者:OIer|zythonc  时间:2020/5/22 2:02:58  对本文有异议

更新记录

【1】2020.05.21-23:49

1.完善矩阵快速幂

正文

由于普通快速幂太过于简单,这里就先不写了,后期再完善吧QAQ
在学习矩阵快速幂之前,我们先来了解一下矩阵这个东西

矩阵的定义:在数学中,矩阵是一个按照长方阵列排列的复数或实数集合

好了相信你已经精通了解了矩阵
接下来让我们接触一下它的运算

矩阵乘法

那么首先我们要明白:不是任意两个矩阵都可以相乘
如果两个矩阵可以相乘,那么其中一个矩阵的行数等于另一个矩阵的列数

举几个例子:

  • 设A为2×3矩阵,B为3×2矩阵,可以相乘
  • 设A为3×4矩阵,B为3×2矩阵,不可相乘
  • 设A为9×4矩阵,B为1×9矩阵,可以相乘
  • 设A为2×3矩阵,B为3×1矩阵,可以相乘

设A为i×k矩阵,B为k×j矩阵,那么其乘积为一个i×j矩阵

之后记公式即可

\(C_{i,j}=\sum\limits_{k=1}^{k}A_{i,k}*B_{k,j}\)

举一个很简单的例子:设A为2×4矩阵,B为4×2矩阵

\(A=\begin{bmatrix}0&1&2&3\\4&5&6&7\end{bmatrix}\)

\(B=\begin{bmatrix}10&11\\12&13\\14&15\\16&17\end{bmatrix}\)

\(A*B=\)

\(\begin{bmatrix}0*10+1*12+2*14+3*16&0*11+1*13+2*15+3*17\\4*10+5*12+6*14+7*16&4*11+5*13+6*15+7*17\end{bmatrix}\)

\(=\begin{bmatrix}88&94\\296&318\end{bmatrix}\)

那么接下来就很简单了,重载一下乘号,原样写代码就可以
(普通快速幂怎么写就怎么写)

#include<iostream>
#include<cstring>
using namespace std;
#define NUM 105
#define MOD 1000000007
#define ll long long
ll n,f;
struct matrix{
	ll a[NUM][NUM];
	matrix() {memset(a,0,sizeof a);}
}m,ans;
matrix operator * (matrix const &A,matrix const &B){
	matrix C;int i,o,p;
	for(i=1;i<=n;i++)
		for(o=1;o<=n;o++)
			for(p=1;p<=n;p++)
				C.a[i][o]=(C.a[i][o]+A.a[i][p]*B.a[p][o]%MOD)%MOD;
	return C;
}
int main(){
	cin>>n>>f;
	int i,o;
	for(i=1;i<=n;i++){
		ans.a[i][i]=1;
		for(o=1;o<=n;o++)
			cin>>m.a[i][o];
	}
	while(f){
		if(f&1) ans=ans*m;
		f>>=1;m=m*m;
	}
	for(i=1;i<=n;i++){
		for(o=1;o<=n;o++)
			cout<<ans.a[i][o]<<" ";
        cout<<"\n";
    }
}

原文链接:http://www.cnblogs.com/zythonc/p/12934491.html

 友情链接: NPS