题解 POJ3318【Matrix Multiplication】

posted on 2022-10-21 19:56:08 | under 题解 | source

problem

判断三个 \(n\times n\) 的矩阵是否满足 \(A\times B=C\)，\(n\leq 500\)。

solution

随机一个行向量 \(v\)。若 \(a\times b=c\)，则有 \(v\times a\times b=v\times c\)（不充分）。显然相乘复杂度仅为 \(O(n^2)\)。类似于一种哈希，正确概率很高。

code

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<int N,int M> struct matrix{
    LL a[N+1][M+1];
    matrix(bool k=0){memset(a,0,sizeof a);for(int i=1;i<=N;i++) a[i][i]=k;}
    LL* operator[](int i){return a[i];}
};
template<int N,int M> bool operator==(matrix<N,M> a,matrix<N,M> b){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if(a[i][j]!=b[i][j]) return 0;
    return 1;
}
template<int N,int M,int R> matrix<N,R> operator*(matrix<N,M> a,matrix<M,R> b){
    matrix<N,R> res;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=R;j++)
            for(int k=1;k<=M;k++)
                res[i][j]=res[i][j]+a[i][k]*b[k][j];
    return res;
}
int n;
matrix<510,510> a,b,c;
matrix<1,510> v[20];
int mian(){
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&b[i][j]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&c[i][j]);
	for(int j=1;j<=5;j++){
		if(!(v[j]*a*b==v[j]*c)) return puts("NO"),0;
	}
	puts("YES");
	return 0;
}
void reset(){
	memset(a.a,0,sizeof a.a);
	memset(b.a,0,sizeof b.a);
	memset(c.a,0,sizeof c.a);
}
int main(){
	srand(time(0));
	for(int i=1;i<=5;i++){
		for(int j=1;j<=500;j++) v[i][1][j]=rand()<<15|rand();
	}
	for(;~scanf("%d",&n);reset(),mian());
	return 0;
}