学习笔记~矩阵快速幂~
程序员文章站
2022-07-05 11:27:25
看了好几遍矩阵快速幂的相关入门资料,写的公式漫天飞的,眼睛都花了也没看懂,为了防止这种事再次发生,特把相关心得记下,下次方便查阅矩阵快速幂=快速幂+矩阵乘法矩阵快速幂就是把快速幂的函数内容换成3层循环的矩阵乘法就这样,完事留一个模板方便下次看#pragma GCC optimize("Ofast","inline","-ffast-math")#pragma GCC target("avx,sse2,sse3,sse4,mmx")#include#d...
看了好几篇矩阵快速幂的相关入门资料,写的公式漫天飞的,眼睛都花了也没看懂,为了防止这种事再次发生,特把相关心得记下,下次方便查阅
矩阵快速幂=快速幂+矩阵乘法
矩阵快速幂就是把快速幂的函数内容换成3层循环的矩阵乘法
就这样,完事
留一个模板方便下次看
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
const int mod=1000000007;
int n,k;
struct node
{
int a[110][110];
node()
{
memset(a,0,sizeof(a));
}
inline void build()
{
for(int i=0; i<n; ++i)
a[i][i]=1;
}
} a,ans;
node operator *(const node &x,const node &y)
{
node z;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
for(int k=0; k<n; ++k)
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
return z;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
cin>>a.a[i][j];
ans.build();
while(k)
{
if(k&1)
ans=ans*a;
k>>=1;
a=a*a;
}
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
cout<<ans.a[i][j]<<" ";
cout<<endl;
}
return 0;
}
P.S.重载运算符之后内容就基本上可以写的和快速幂一样了
本文地址:https://blog.csdn.net/qq_43586463/article/details/107166251
下一篇: 安卓开发中常用的依赖(常更新)
推荐阅读
-
FZU2018级算法第一次作业 1.1fibonacci (矩阵快速幂)
-
2018年湘潭大学程序设计竞赛G又见斐波那契(矩阵快速幂)
-
HDU 2256Problem of Precision(矩阵快速幂)
-
洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
-
POJ3233Matrix Power Series(矩阵快速幂)
-
BZOJ1898: [Zjoi2005]Swamp 沼泽鳄鱼(矩阵快速幂)
-
BZOJ2476: 战场的数目(矩阵快速幂)
-
矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解
-
矩阵乘法(二):利用矩阵快速幂运算完成递推
-
Recursive sequence(HDU5950 矩阵快速幂)