求助矩阵快速幂
  • 板块学术版
  • 楼主wmq2006
  • 当前回复40
  • 已保存回复40
  • 发布时间2020/5/5 21:11
  • 上次更新2023/11/7 03:04:22
查看原帖
求助矩阵快速幂
330026
wmq2006楼主2020/5/5 21:11

RT,全WA了,求查错QAQ

#include<bits/stdc++.h>
using namespace std;
struct matrix{
	long long a[101][101];
}ans,t;
int n,k;
int mod=1e9+7;
matrix operator *(matrix aa,matrix bb){
	matrix v;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			long long r=0;
			for(int k=1;k<=n;k++){
				r+=aa.a[i][k]*bb.a[k][j];
				r%=mod;
			}
			v.a[i][j]=r%mod;
		}
	}
	return v;
} 
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>t.a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j)ans.a[i][j]=0;
			else ans.a[i][j]=1;
		}
	}
	while(k){
		if(k&1){
			ans=ans*t;
		}
		t=t*t;
		k/=2;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<ans.a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}
2020/5/5 21:11
加载中...