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
2
1 0
2 3
5 1
0 8
5 1
10 26
Sample Output
YES
Hint
Multiple inputs will be tested. So O(n3) algorithm will get TLE.
Source
给定矩阵A和B，判断矩阵C是不是它们的乘积。
题目明确表示直接判断会超时，而Strass和直接相乘的O（n^3）效果相差不多。
因而采用随机化方法，按我自己的想法，随机测试C中的若干元素，以确定结果，看了讨论区，才发现有更加“专业”的办法。
随机生成行向量I，则若A*B=C，那么必有I*A*B=I*C；反之，不一定成立，算法的随机性正体现在这里。
用一个必要不充分条件来判断结果的正确性，比盲目测试效果往往要好得多。
这个必要条件判断结果的时间复杂度是O（N^2）的，这是题目输入数据量可以接受的。
/**//*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;
}