矩阵快速幂板子求调qwq
  • 板块灌水区
  • 楼主Bicycle_zxc
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/1 22:26
  • 上次更新2024/5/2 10:55:40
查看原帖
矩阵快速幂板子求调qwq
710345
Bicycle_zxc楼主2024/5/1 22:26

rt,一个点 MLE。

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long n,k;
struct Matrix{
	long long Mat[105][105];
}tmp,a;
Matrix operator *(Matrix a,Matrix b){
	Matrix c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				c.Mat[i][j]+=a.Mat[i][k]*b.Mat[k][j];
				c.Mat[i][j]%=mod;
			}
		}
	}
	return c;
}
Matrix tmplol;
inline Matrix ksm(Matrix a,long long k){
    if(k==1){
        return a;
    }
	if(k%2==0){
		tmplol=ksm(a,k/2);
		return tmplol*tmplol;
	}
	else{
        tmplol=ksm(a,k/2);
        return tmplol*tmplol*a;
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a.Mat[i][j];
		}
	}
	tmp=ksm(a,k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<tmp.Mat[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}
2024/5/1 22:26
加载中...