题目描述

Description

给出三个行数和列数均为N的矩阵A、B、C，判断A*B=C是否成立。

Input

题目可能包含若干组数据。
对于每组数据，第一行一个数N，接下来给出三个N*N的矩阵，依次为A、B、C三个矩阵。

Output

对于每组数据，若A*B=C成立，则输出Yes，否则No。每个答案占一行。

Sample Input

1
2
2
100

Sample Output

No

HINT

对于90%的数据，N不超过100；
对于100%的数据，N不超过1000，矩阵中的数字大于等于0小于1000，数据组数不超过5组。

题目分析

正常矩阵乘法是的时间复杂度 过不去
注意到矩乘不满足交换律 但是矩乘满足结合律
这样的话 我们先随机生成一个的矩阵a
本题要求判断给定的矩阵是否满足
如果上式成立的话 在等号两边左乘一个矩阵a 等号必定成立
即:
根据结合律,即
这样的话 复杂度降为了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
int tmp[1010];
int a[1010][1010],b[1010][1010],c[1010][1010];
int ans1[1010],ans2[1010];
int nmp[1010];
void mul1()
{   
    memset(nmp,0,sizeof nmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            nmp[i]+=tmp[j]*a[j][i];
    for(int i=1;i<=n;i++) ans1[i]=nmp[i];
}
void mul2()
{
    memset(nmp,0,sizeof nmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            nmp[i]+=ans1[j]*b[j][i];
    for(int i=1;i<=n;i++) ans1[i]=nmp[i];
}
void mul3()
{
    memset(nmp,0,sizeof nmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            nmp[i]+=tmp[j]*c[j][i];
    for(int i=1;i<=n;i++) ans2[i]=nmp[i];   
}
int judge()
{
    for(int i=1;i<=n;i++) 
        if(ans1[i]!=ans2[i]) return 0;
    return 1;
}
int main()
{   
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) tmp[i]=rand();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) 
                scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) 
                scanf("%d",&b[i][j]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) 
                scanf("%d",&c[i][j]);
        mul1(),mul2(),mul3();
        if(judge()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}