pku3318source.cpp

PKU3318代码 随机化算法在检验矩阵乘法时的应用

//PKU2078Source 
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;


long A[510][510];
long B[510][510];
long C[510][510];
long X[510][510];
long R1[510][510];
long R2[510][510];
long T[510][510];
int n;
void matrix_mul(long a[510][510],long b[510][510],long c[510][510],int ax,int ay,int bx,int by)
{
	int i,j,k;
	for(i=1;i<=by;i++){
		for(j=1;j<=ax;j++){
			c[j][i]=0;
			for(k=1;k<=bx;k++){
				c[j][i]+=a[j][k]*b[k][i];
			}
		}
	}

}

int test()
{

	int i,j;
	for(i=1;i<=n;i++){
		long rnd=rand()%10000;
		X[i][1]=rnd;
	}

	matrix_mul(B,X,T,n,n,n,1);
	matrix_mul(A,T,R1,n,n,n,1);
	matrix_mul(C,X,R2,n,n,n,1);

	for(i=1;i<=n;i++){
		if(R2[i][1]!=R1[i][1]){
		
			return 0;
		}
	}

	return 1;
}

int main()
{

//	freopen("input.in","r",stdin);


	srand( (unsigned)time( NULL ) ); 

	int i,j;
	while(cin>>n){
		for(i=1;i<=n;i++){		
			for(j=1;j<=n;j++)
				scanf("%ld",&A[i][j]);
		}
		for(i=1;i<=n;i++){		
			for(j=1;j<=n;j++)
				scanf("%ld",&B[i][j]);
		}
		for(i=1;i<=n;i++){		
			for(j=1;j<=n;j++)
				scanf("%ld",&C[i][j]);
		}

		for(i=1;i<=4;i++)
			if(!test()){
				cout<<"NO"<<endl;
				break;
			}

		if(i==5)
			cout<<"YES"<<endl;

	}


	return 0;
}