51Nod1140 矩阵相乘结果的判断

Problem

给出三个N*N的矩阵A, B, C，问A * B是否等于C？

Solution

随机找或者用向量压缩。

Code

#include<stdio.h>
#include<iostream>
#include <time.h>
#include <stdlib.h>
#define ll long long
using namespace std;
int n;
int a[520][520],b[520][520],c[520][520];
int r[520],r2[520];
int cr[520],rc[520],br[520],ra[520],abr[520],rab[520];
bool rd(){
	srand(time(NULL));
	int x;
	int y;
	for(int i=1;i<=30000;i++){
		x=rand()%n+1;
		y=rand()%n+1;
		int sum=0;
		for(int j=1;j<=n;j++){
			sum+=a[x][j]*b[j][y];
		} 
		if(sum!=c[x][y]) return false;
	}
	return true;
}
int main(){
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&c[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		r[i]=i*i%101;
		r2[i]=(i+3)*i%111;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cr[i]+=c[i][j]*r[j];
			rc[i]+=c[j][i]*r2[j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			br[i]+=b[i][j]*r[j];
			ra[i]+=a[j][i]*r2[j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			abr[i]+=a[i][j]*br[j];
			rab[i]+=b[j][i]*ra[j];
		}
	}
	bool f=true;
	for(int i=1;i<=n;i++){
		if(abr[i]!=cr[i]||rab[i]!=rc[i]){
			f=false;
			break;
		}
	}
	//cout<<rd();
	if(!f){
		printf("No
");
	}
	else{
		//f=f&rd();
		//if(f){
			printf("Yes
");
		//}
		//else{
			//printf("No
");
		//}
		
	}
	return 0;
}