poj 3318

题目中明确交代，0（n ^ 3) 会 TLE，可是一开始还就没看见，以为在计算矩阵时加两个优化可在 2s 挤过去呢，然后就TLE了三次，看别人的说是有一个结论 A * B * X == C * X时，有 A * B == C成立（成立的概率很大），然后 X 就是用随机函数求的

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <math.h>
 7 #define N 510
 8 #define mod 10000
 9 #define _clr(a,val) (memset(a,val,sizeof(a)))
10 
11 using namespace std;
12 
13 typedef long long ll;
14 
15 int a[N][N],b[N][N],c[N][N];
16 int ta[N],tb[N],tc[N];
17 int n;
18 int main()
19 {
20     int i,j;
21     //freopen("data.txt","r",stdin);
22     while(cin>>n)
23     {
24         for(i = 1; i <= n; i++)
25         {
26             for(j = 1; j <= n; j++)
27             scanf("%d",&a[i][j]);
28         }
29         for(i = 1; i <= n; i++)
30         {
31             for(j = 1; j <= n; j++)
32             scanf("%d",&b[i][j]);
33         }
34         for(i = 1; i <= n; i++)
35         {
36             for(j = 1; j <= n; j++)
37             scanf("%d",&c[i][j]);
38         }
39         for(i = 1; i <= n; i++)
40         ta[i] = i;  // ta [i] = rand() % 101 也可以
41         for(i = 1; i <= n; i++)
42         {
43             tc[i] = 0;
44             tb[i] = 0;
45             for(j = 1; j <= n; j++)
46             {
47                 tc[i] += c[i][j] * ta[j];
48                 tb[i] += b[i][j] * ta[j];
49             }
50         }
51         for(i = 1; i <= n; i++)
52         {
53             ta[i] = 0;
54             for(j = 1; j <= n; j++)
55             ta[i] += a[i][j] * tb[j];
56         }
57         //int flag = 1;
58         for(i = 1; i <= n; i++)
59         {
60             if(tc[i] != ta[i])
61             {
62                 //flag = 1;
63                 cout<<"NO\n";
64                 break;
65             }
66         }
67         if(i == n + 1) cout<<"YES\n";
68     }
69     return 0;
70 }