51Nod1140 矩阵相乘的结果

随机化算法。
A*B==C那么X*A*B==X*C
降到了n*n复杂度。
多次随机X判断即可。
By：大奕哥
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int a[5][505],b[5][505],c[5][505],x[5][505];
 5 int main()
 6 {
 7     scanf("%d",&n);int k;
 8     for(int i=1;i<=n;++i)
 9     {
10         for(int zz=1;zz<=2;++zz)
11         {
12             x[zz][i]=rand()%10000+2;
13         }
14     }
15     for(int i=1;i<=n;++i)
16         for(int j=1;j<=n;++j)
17         {
18             scanf("%d",&k);
19             for(int zz=1;zz<=2;++zz)
20             {
21                 a[zz][j]+=x[zz][i]*k;
22             }
23         }
24     for(int i=1;i<=n;++i)
25         for(int j=1;j<=n;++j)
26         {
27             scanf("%d",&k);
28             for(int zz=1;zz<=2;++zz)
29             {
30                 b[zz][j]+=a[zz][i]*k;
31             }
32         }
33     for(int i=1;i<=n;++i)
34         for(int j=1;j<=n;++j)
35         {
36             scanf("%d",&k);
37             for(int zz=1;zz<=2;++zz)
38             {
39                 c[zz][j]+=x[zz][i]*k;
40             }
41         }
42     for(int i=1;i<=n;++i)
43         for(int j=1;j<=n;++j)
44         {
45             for(int zz=1;zz<=2;++zz)
46             {
47                 if(b[zz][j]!=c[zz][j])
48                 {puts("No");return 0;}
49             }
50         }
51     puts("Yes");
52     return 0;
53 }