51nod 1140 矩阵相乘结果的判断

给出三个N*N的矩阵A, B, C，问A * B是否等于C？

Input

第1行，1个数N。(0 <= N <= 500)

第2 - N + 1行：每行N个数，对应矩阵A的元素。（0 <= M[i] <= 16)

第N + 2 - 2N + 1行：每行N个数，对应矩阵B的元素。（0 <= M[i] <= 16)

第2N + 2 - 3N + 1行：每行N个数，对应矩阵C的元素。

Output

如果相等输出Yes，否则输出No。

Input示例

Output示例

Yes
——————————————————————
这题如果直接乘a b矩阵要 n^3 方 那么肯定会T
我们可以考虑引进一个向量 也就是1*n的矩阵 和 a b c 乘起来
判断是否相等就可以辣 这样是n^2的复杂度 
如果担心不准 可以多rand几个1*n的矩阵多次比较

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::max;

const int M=;

char buf[*M*M],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

int n;

typedef int mat[M][M];

mat a,b,c;

int ly[M],yy[M],tmp[M];

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=read();

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) a[i][j]=read();

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) b[i][j]=read();

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) c[i][j]=read();

    for(int i=;i<=n;i++) ly[i]=rand();

    for(int i=;i<=n;i++) yy[i]=ly[i];

    for(int k=;k<=n;k++) for(int j=;j<=n;j++) tmp[k]+=ly[j]*a[j][k];

    for(int i=;i<=n;i++) ly[i]=tmp[i];

    memset(tmp,,sizeof(tmp));

    for(int k=;k<=n;k++) for(int j=;j<=n;j++) tmp[k]+=ly[j]*b[j][k];

    for(int i=;i<=n;i++) ly[i]=tmp[i];

    memset(tmp,,sizeof(tmp));

    for(int k=;k<=n;k++) for(int j=;j<=n;j++) tmp[k]+=yy[j]*c[j][k];

    for(int i=;i<=n;i++)if(ly[i]!=tmp[i]) return puts("No"),;

    puts("Yes");

    return ;

}

巴特西

51nod 1140 矩阵相乘结果的判断

最新文章

热门文章