TLE求助
查看原帖
TLE求助
477032
diandian2020楼主2023/9/27 17:45

改了输出还是没用

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=45,P=10;
int n,k;
struct mat{
	int a[N][N];
	mat(){
		memset(a,0,sizeof(a));
	}
	void init(){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a[i][j]=i==j;
	}
	mat operator+(const mat &W)const{
		mat res;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				res.a[i][j]=(a[i][j]+W.a[i][j])%P;
		return res;
	}
	mat operator*(const mat &W)const{
		mat res;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++)
					res.a[i][j]+=a[i][k]*W.a[k][j];
				res.a[i][j]%=P;
			}
		return res;
	}
	void print(){
		for(int i=1;i<=n;i++,puts(""))
			for(int j=1;j<=n;j++){
				if(j>1) printf(" ");
				printf("%d",a[i][j]);
			}
	}
}A,F[25],S[25]; 
int main(){
	while(scanf("%d%d",&n,&k),n||k){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				LL x; scanf("%lld",&x);
				A.a[i][j]=x%P;
			}
		F[0]=S[0]=A;// puts("0:\n"); F[0].print(),S[0].print();
		for(int i=1;1<<i<=k;i++){
			F[i]=F[i-1]*F[i-1],S[i]=S[i-1]+F[i-1]*S[i-1];
//			printf("%d:\n",i);
//			F[i].print(),S[i].print();
		}
		mat res,cur; cur.init();
		for(int i=20;i>=0;i--)
			if(k>>i&1){
//				printf("--%d:\n",i);
//				mat t=cur*S[i];
//				t.print();
				res=res+cur*S[i];
				cur=cur*F[i];
//				cur.print(),res.print();
			}
		res.print(); puts("");
	}
	return 0;
}
2023/9/27 17:45
加载中...