北大 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思路:若用常规方法做肯定超时,这里采用随机抽取行列序号进行检测,随机次数越多正确率越高

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}