JZOJ 3508. 【NOIP2013模擬11.5B組】好元素

3508. 【NOIP2013模擬11.5B組】好元素(good) 
(File IO): input:good.in output:good.out

輸入1：

2

1 3

輸入2：

6

1 2 3 5 7 10

輸入3：

3

-1 2 0

輸出1：

1

輸出2：

4

輸出3：

1

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define N 5007
 7 #define mo 14150547
 8 #define z 2000000000
 9 #define LL long long
10 using namespace std;
11 LL n, a[N], h[mo + 1];
12 int ans;
13 bool f;
14 
15 LL hash(LL x)
16 {
17     LL p = x % mo;
18     while (h[p] != 0 && h[p] != x - z && p <= mo)    p = (p + 1) % mo;
19     return p;
20 }
21 
22 void work()
23 {
24     for (int i = 1; i <= n; i++)
25     {
26         for (int j = 1; j < i; j++)
27             if (h[hash(a[i] - a[j] + z)] == a[i] - a[j] && a[i] - a[j] != 0)
28             {
29                 ans++;
30                 break;
31             }
32             else if (a[i] - a[j] == 0)
33             {
34                 if (f)
35                 {
36                     ans++;
37                     break;
38                 }
39             }
40         for (int j = 1; j <= i; j++)
41         {
42             LL p = (a[i] + a[j] + z) % mo;
43             while (h[p] != a[i] + a[j] && h[p] != 0 && p <= mo)    p = (p + 1) % mo;
44             if (a[i] + a[j] != 0)    h[p] = a[i] + a[j];
45             else f = true;
46         }
47     }
48 }
49 
50 int main()
51 {
52     freopen("good.in", "r", stdin);
53     freopen("good.out", "w", stdout);
54     scanf("%lld", &n);
55     for (int i = 1; i <= n; i++)
56         scanf("%lld", &a[i]);
57     work();
58     cout << ans;    
59 }