矩阵快速幂模板RE了,求助
查看原帖
矩阵快速幂模板RE了,求助
102709
zjy1412楼主2020/11/11 07:52

RE得莫名奇妙,代码很短,帮忙看一下,谢谢!

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
using namespace std;
#define int long long
#define R register
#define debug printf("zjy ")
#define ld double
#define pii pair<int,int> 
#define fir first
#define sec second
#define mp(x,y) make_pair(x,y)
int read(){
	int a=0,b=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')b=-1;c=getchar();}
	while(isdigit(c)){a=a*10+c-'0';c=getchar();}
	return a*b;
}
void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x<=9){putchar(x+'0');return;}
	write(x/10);putchar(x%10+'0');
}
void writesp(int x){
	write(x);putchar(' ');
}
void writeln(int x){
	write(x);putchar('\n');
}
const int N=150,P=1e9+7;
int n,K;
struct map{
	int f[N][N];
	map operator *(const map x){
		static map zxt;
		memset(zxt.f,0,sizeof(zxt.f));
		for(R int k=1;k<=n;k++){
			for(R int i=1;i<=n;i++){
				for(R int j=1;j<=n;j++){
					zxt.f[i][j]+=f[i][k]*x.f[k][j]%P;
					zxt.f[i][j]%=P;
				}
			}
		}
	}
}b,ans;
void doit(){
	K--;
	ans=b;
	while(K){
		if(K&1)ans=ans*b;
		b=b*b;
		K>>=1;
	}
}
signed main(){
	n=read();K=read();
	for(R int i=1;i<=n;i++){
		for(R int j=1;j<=n;j++){
			b.f[i][j]=read()%P;
		}
	}
	for(R int i=1;i<=n;i++){
		for(R int j=1;j<=n;j++){
			if(i==j)ans.f[i][j]=1;
			else ans.f[i][j]=0;
		}
	}
	doit();
	for(R int i=1;i<=n;i++){
		for(R int j=1;j<n;j++){
			writesp(ans.f[i][j]);
		}
		writeln(ans.f[i][n]);
	}
	return 0;
}
2020/11/11 07:52
加载中...