求调矩阵快速幂
  • 板块学术版
  • 楼主Chancylaser
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/5/2 08:27
  • 上次更新2023/11/4 23:52:11
查看原帖
求调矩阵快速幂
241817
Chancylaser楼主2021/5/2 08:27

不说了,快调崩溃了,求大佬解答 代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k;
struct jv{
	int n,m;
	int z[233][233];
	jv(){
		n=0,m=0;
		memset(z,0,sizeof(z));
	} 
};
jv operator*(const jv &m1,const jv &m2){     
	jv m3;
	m3.n=m1.n;
	m3.m=m2.m;
	for(int i=1;i<=m3.n;i++)
		for(int j=1;j<=m3.m;j++)
			for(int k=1;k<=m1.m;k++)
				m3.z[i][j]+=m1.z[i][k]*m2.z[k][j];
	return m3;
}
typedef long long ll;
jv qp(jv &x,ll nd){
	jv res;
	memset(res.z,0,sizeof(res.z));
	res.n=n;
	res.m=n;
	for(int i=1;i<=n;i++)
		res.z[i][i]=1;
	while(nd>0){
		if(nd&1)	res=res*x;
		x=x*x;
		nd>>=1;
	}
	return res;
}
int main(){
	cin>>n>>k;
	jv a;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a.z[i][j];
	jv b=qp(a,k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cout<<b.z[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}
2021/5/2 08:27
加载中...