难度上。，，确实。。。不算难

问题是有个矩阵运算的优化

题目是说给个N*K的矩阵A给个K*N的矩阵B（1<=N<=1000 && 1=<K<=6），先把他们乘起来乘为C矩阵。然后算C^(N*N)

相当于

ABABABABABABAB...=(AB)^(N*N)

不如

A(BA)^(N*N-1)B

由于BA乘得K*K的矩阵，K是比較小的

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

using namespace std;

int a[1111][1111];

int b[1111][1111];

int c[1111][1111];

int tmp[1111][1111];

int sum[1111][1111];

void TIMES(int K,int N,int M,int aa[][1111],int bb[][1111],int cc[][1111]){

	memset(tmp,0,sizeof(tmp));

	for(int i=1;i<=K;i++){

		for(int j=1;j<=M;j++){

			for(int k=1;k<=N;k++){

				tmp[i][j]=(tmp[i][j]+aa[i][k]*bb[k][j]%6)%6;

			}

		}

	}

	for(int i=1;i<=K;i++)

		for(int j=1;j<=M;j++)

			cc[i][j]=tmp[i][j]%6;

}

void quick(int cc[][1111],int mi,int n){

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			if(i==j) sum[i][j]=1;

			else sum[i][j]=0;

	while(mi){

		if(mi&1)

			TIMES(n,n,n,cc,sum,sum);

		TIMES(n,n,n,cc,cc,cc);

		mi>>=1;

	}

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("G:/in.txt","r",stdin);

	//freopen("G:/myout.txt","w",stdout);

#endif

	int N,K;

	while(~scanf("%d%d",&N,&K)){

		if(N==0 && K==0) return 0;

		for(int i=1;i<=N;i++){

			for(int j=1;j<=K;j++){

				scanf("%d",&a[i][j]);

			}

		}

		for(int i=1;i<=K;i++){

			for(int j=1;j<=N;j++){

				scanf("%d",&b[i][j]);

			}

		}

		TIMES(K,N,K,b,a,c);

		quick(c,N*N-1,K);

		TIMES(N,K,K,a,sum,sum);

		TIMES(N,K,N,sum,b,sum);

		int ans=0;

		for(int i=1;i<=N;i++)

			for(int j=1;j<=N;j++)

				ans+=sum[i][j];

		cout<<ans<<endl;

	}

}