数学（矩阵乘法，随机化算法）：POJ 3318 Matrix Multiplication

Matrix Multiplication

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 17783		Accepted: 3845

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

Sample Output

YES

Hint

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

　　用个一维随机矩阵去乘再判断是否相等，类似与哈希的思想。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 using namespace std;
 6 const int maxn=250010;
 7 struct Array{
 8     int a[maxn],L;
 9     int *operator[](int x){
10         return &a[(x-1)*L];
11     }
12 };
13 struct Matrix{
14     int R,C;
15     Array mat;
16     Matrix(){
17         memset(mat.a,0,sizeof(mat.a));
18         R=C=0;
19     }
20     void Init(int r,int c){
21         R=r;mat.L=C=c;
22     }
23     int *operator[](int x){
24         return mat[x];
25     }
26     friend Matrix operator*(Matrix a,Matrix b){
27         Matrix c;c.Init(a.R,b.C);
28         for(int i=1;i<=a.R;i++)
29             for(int j=1;j<=b.C;j++)
30                 for(int k=1;k<=a.C;k++)
31                     c[i][j]+=a[i][k]*b[k][j];
32         return c;            
33     }
34     friend bool operator ==(Matrix a,Matrix b){
35         if(a.R!=b.R||a.C!=b.C)return false;
36         for(int i=1;i<=a.R;i++)
37             for(int j=1;j<=b.C;j++)
38                 if(a[i][j]!=b[i][j])
39                     return false;
40         return true;            
41     }
42 }A,B,C,D;
43 int main(){
44     int n,x;
45     scanf("%d",&n);srand(n);
46     A.Init(n,n);
47     B.Init(n,n);
48     C.Init(n,n);
49     D.Init(n,1);
50     for(int i=1;i<=n;i++)
51         D[i][1]=rand();
52     for(int i=1;i<=n;i++){
53         for(int j=1;j<=n;j++){
54             scanf("%d",&x);
55             A[i][j]=x;
56         }
57     }
58     for(int i=1;i<=n;i++){
59         for(int j=1;j<=n;j++){
60             scanf("%d",&x);
61             B[i][j]=x;
62         }
63     }
64     for(int i=1;i<=n;i++){
65         for(int j=1;j<=n;j++){
66             scanf("%d",&x);
67             C[i][j]=x;
68         }
69     }
70     A=A*(B*D);
71     C=C*D;
72     if(A==C)
73         printf("YES
");
74     else
75         printf("NO
");
76     return 0;    
77 }