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