【数学】Matrix Multiplication

时间:2022-02-13 10:50:36
                             Matrix Multiplication
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 18173   Accepted: 3912

Description

You are given three n × n matrices AB 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 AB and 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

2
1 0
2 3
5 1
0 8
5 1
10 26

Sample Output

YES

Hint

Multiple inputs will be tested. So O(n3) algorithm will get TLE.
试题分析:
    首先,最暴力的方法显然就是求一遍A*B,然后与C对照,但是这样效率太低
    So O(n3) 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";
}