暴力矩阵乘法显然会TLE。
那么我们随机一个1*n的矩阵D，然后利用矩阵运算的结合律$A*B*D=A*(B*D)$，然后就可以快速判断了。
这样操作完错误率是很低的。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
struct Matrix{
int Mt[N][N];
}A,B,C;
int n,Tp1[N],Tp2[N];
void Mul(int *r,Matrix T){
int Tp[N];
for(int i=1;i<=n;i++){
Tp[i]=0;
for(int j=1;j<=n;j++){
Tp[i]+=r[j]*T.Mt[j][i];
}
}
for(int i=1;i<=n;i++)r[i]=Tp[i];
}
int main(){
freopen("2396.in","r",stdin);
freopen("2396.out","w",stdout);
srand(233);
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++)Tp1[i]=Tp2[i]=rand();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&A.Mt[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&B.Mt[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&C.Mt[i][j]);
}
}
Mul(Tp1,A);
Mul(Tp1,B);
Mul(Tp2,C);
int flag=1;
for(int i=1;i<=n;i++)if(Tp1[i]!=Tp2[i]){flag=0;break;}
puts(flag?"Yes":"No");
}
return 0;
}
评论 (0)
