【数学】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 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

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";

}

　　

相关文章