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。

H*A*B=H*C

随机几个H看能不能满足这个式子就好啦。

// 1140matrixmultiply.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

const int maxn=1e3+5;
const int maxx=1e5+100;

int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
int ans1[maxn],ans2[maxn],ans3[maxn],rnd[maxn];
int n;

inline int Scan()
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
       flag=1;
    else if(ch>='0' && ch<='9')
       res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
       res=res*10+ch-'0';
    return flag ? -res : res;
}
int main(int argc, char* argv[])
{
    //srand();
   int i,j,cnt;
   if(NULL==freopen("51nod1140i.txt","r",stdin))
      return -1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for (j=1; j<=n; j++)
            a[i][j]=Scan();
    for(i=1;i<=n;i++)
        for (j=1; j<=n; j++)
            b[i][j]=Scan();
    for(i=1;i<=n;i++)
        for (j=1; j<=n; j++)
            c[i][j]=Scan();
    cnt=20;
    while(cnt--){
        memset(ans1,0,sizeof(ans1));
        memset(ans2,0,sizeof(ans2));
        memset(ans3,0,sizeof(ans3));
        for(i=1;i<=n;i++)
            rnd[i]=(long long)rand()%16;
        for(i=1;i<=n;i++)
            for (j=1; j<=n; j++)
                ans1[i]+=rnd[j]*a[j][i];
         for(i=1;i<=n;i++)
            for (j=1; j<=n; j++)
                ans2[i]+=ans1[j]*b[j][i];
         for(i=1;i<=n;i++)
            for (j=1; j<=n; j++)
                ans3[i]+=rnd[j]*c[j][i];
        for(i=1;i<=n;i++)
            if(ans2[i]!=ans3[i]){
               puts("No");
               return 0;
            }
    }
    puts("Yes");
    return 0;
}
/*
IN:
2
1 0
0 1
0 1
1 0
0 1
1 0
OUT:
Yes
*/