【数学】Matrix Multiplication

Matrix Multiplication

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 18173		Accepted: 3912

Description

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

Input

The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix's description is a block of n × n integers.

It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.

Output

Output "YES" if the equation holds true, otherwise "NO".

Sample Input

Sample Output

YES

Hint

Multiple inputs will be tested. So O(n³) algorithm will get TLE.

试题分析：

首先，最暴力的方法显然就是求一遍A*B，然后与C对照，但是这样效率太低

So O(n³) algorithm will get TLE.

所以不可取

那么我们设想一个随机生成的向量V，其每个元素都在1和0中选取

考察A*(B*v)=? C

但是我们说只执行一遍正确性是很可悲的

设想如果A*B！=C那么就说明A*B-C！=0

那么说明A*B-C完了的数组至少有一个非0

但是如果所在的这列正好V为0呢？

我们知道：若A=B，则A*N=B*N

但是如果反过来说A*N=B*N那么A=B，这就不对了，因为N有可能是0

我们继续思考这个简单的问题，那么如果将A*N=B*N这个N等概率地取几次任意值，那么基本上就不会出错了

这里也一样，因为每个元素都在1和0中选取，所以算法正确性只有1/2

我们可以采取多试几次或者扩大向量V的取值范围来提高算法的正确性

由于在A*B！=C的情况下，A*B-C完了的数组至少有一个非0

但这只是极端情况，所以个人认为还是多试几次好

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<time.h>
#include<stdlib.h> 
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
int A[501][501],B[501][501],C[501][501];
int N;
int Num[1001],Num2[1001];//压缩后的A*(B*V) 压缩后的V*C 
int Fk[1001];//向量V 
int tmp;
int main(){
	N=read();
	
	for(int i=1;i<=N;i++)
	    for(int j=1;j<=N;j++)
	        A[i][j]=read();
	for(int i=1;i<=N;i++)
	    for(int j=1;j<=N;j++)
	        B[i][j]=read();
	for(int i=1;i<=N;i++)
	    for(int j=1;j<=N;j++)
	        C[i][j]=read();
	        
	for(tmp=1;tmp<=60;tmp++){
		memset(Fk,0,sizeof(Fk));
		memset(Num,0,sizeof(Num));
		memset(Num2,0,sizeof(Num2));
		for(int j=1;j<=N;j++) Fk[j]=(rand()*rand()+rand())%2;//随机 
		for(int j=1;j<=N;j++)
		    for(int k=1;k<=N;k++)
		       Num[j]+=C[j][k]*Fk[k];//压缩C*V 
		for(int j=1;j<=N;j++)
		    for(int k=1;k<=N;k++)
		        Num2[j]+=B[j][k]*Fk[k];//压缩(B*V) 
		for(int j=1;j<=N;j++) Fk[j]=Num2[j],Num2[j]=0;
		for(int j=1;j<=N;j++)
		    for(int k=1;k<=N;k++)  
		        Num2[j]+=A[j][k]*Fk[k];//(B*V)*A 
		int L=1;
		for(L=1;L<=N;L++)
		    if(Num[L]!=Num2[L]) break;
		if(L<=N) break;
	}
	
	if(tmp<=60) cout<<"NO";
	else cout<<"YES";
}