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;
}