POJ 3318 Matrix Multiplication (随机化）

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(n ³) algorithm will get TLE.

题解：

　　给你三个n*n的矩阵A、B、C，问你A*B是不是等于C。数据保证O(n^3)铁定超时，因此你需要想一个不用把A和B乘起来就可以验证的算法。一个基于概率的算法是随机生成一个n乘1的矩阵R，然后判断A*B*R是否等于C*R，而前者相当于A*(B*R)，与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等，几乎可以肯定A*B和C也是相等的。

C++：

#include<iostream>
#include<ctime>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=505;
int r[maxn],A[maxn][maxn],B[maxn][maxn],C[maxn][maxn],rA[maxn],rAB[maxn],rC[maxn];
int n;
void input(int mat[maxn][maxn])
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&mat[i][j]);
}
bool check()
{
    for(int j=0;j<n;j++)
        for(int i=0;i<n;i++)
        {
            rA[j]+=r[i]*A[i][j];
            rC[j]+=r[i]*C[i][j];
        }
    for(int j=0;j<n;j++)
        for(int i=0;i<n;i++)
            rAB[j]+=rA[i]*B[i][j];
    for(int i=0;i<n;i++)
        if(rAB[i]!=rC[i])
            return false;
    return true;
}
int main()
{
    cin>>n;
    srand(time(NULL));
    input(A);
    input(B);
    input(C);
    for(int i=0;i<n;i++)
        r[i]=rand()%99+1;
    if(check())
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0; 
}