北大 acm 3318 Matrix Multiplication 解题报告

Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 10444 Accepted: 2089

Description

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

Input

The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix’s description is a block of n × n integers.

It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.

Output

Output “YES” if the equation holds true, otherwise “NO”.

Sample Input

21 02 35 10 85 110 26

Sample Output

YES

题意简单：检查矩阵A、B相乘是否等于C思路：若用常规方法做肯定超时，这里采用随机抽取行列序号进行检测，随机次数越多正确率越高

代码

#include <iostream>
#include <ctime>

using namespace std;

long n,i,j,m,s,k,a[505][505],b[505][505],c[505][505],sum;

int main()
{
  srand((unsigned)time(0))；//初始化随机函数

  while(cin>>n)
  {
    k=0;   

    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        scanf("%d",&a[i][j]);   

    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        scanf("%d",&b[i][j]);

    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        scanf("%d",&c[i][j]);  

    for(s=0;s<60000;s++) //随机次数越多越准确
    {
      j=rand()%n; //随机抽取行列
      i=rand()%n;

      sum=0;   

      for(m=0;m<n;m++)
        sum+=a[i][m]*b[m][j];     

      if(c[i][j]!=sum)
      {
        k=1;
        break;
      }    
    }

    if(k==1)
      cout<<"NO"<<endl;
    else
      cout<<"YES"<<endl;
  }
  return 0;
}