• 如果喜欢本站，您可以按CTRL+D收藏本站，方便下次访问。

• 欢迎来自五湖四海的朋友，期待为您分享有价值的资源

# POJ 3318 Matrix Multiplication 随机化算法

10年前 (2010-08-27) 271次浏览

Matrix Multiplication

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 11924 Accepted: 2408

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

<pre class="sio">2
1 0
2 3
5 1
0 8
5 1
10 26

Sample Output

<pre class="sio">YES

Hint

Multiple inputs will be tested. So O(n3) algorithm will get TLE.

Source

/*Source Code

Problem: 3318  User: y09
Memory: 3080K  Time: 1063MS
Language: C  Result: Accepted

Source Code */
#include <stdio.h>
#include <time.h>
#include<stdlib.h>
int main()
{
int n;
int i,j;
int mat1[500][500];
int mat2[500][500];
int mat3[500][500];
__int64 te1[500]={0};
__int64 te2[500]={0};
__int64 te3[500]={0};
__int64 te4[500]={0};
time_t t;
srand((unsigned) time(&t));
scanf(“%d“,&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf(“%d“,&mat1[i][j]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf(“%d“,&mat2[i][j]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf(“%d“,&mat3[i][j]);
for(i=0;i<n;i++)
te1[i]=rand()%100;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
te2[i]+=te1[j]*mat1[j][i];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
te3[i]+=te2[j]*mat2[j][i];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
te4[i]+=te1[j]*mat3[j][i];
for(i=0;i<n;i++)
if(te3[i]!=te4[i])
{
puts(“NO“);
return 0;
}
puts(“YES“);

return 0;
}


====
• 版权声明

本站的文章和资源来自互联网或者站长的原创，按照 CC BY-NC-SA 4.0 CN协议发布和共享，转载或引用本站文章应保留来源网址，并遵循相同协议。如果有侵犯版权的资源请尽快联系站长，我们会在24H内删除有争议的资源。
• 网站驱动

• 友情链接

• 支持一下