[数组hash] PKU 3274 Gold Balanced Lineup

数组hash：hash的是排列，不能用相加、相乘取模，常用hash函数的资料；
 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 # define get(x, i) ((((x)>>(i))&0x1) ? 1:0)
 5 
 6 # define N 100005
 7 # define K 35
 8 # define MOD 100007
 9 
10 int sum[N][K], c[N][K], a[N], h[MOD << 3];
11 
12 int Max(int x, int y)
13 {
14     return x > y ? x : y;
15 }
16 
17 int eql(int *s, int *t, int k)
18 {
19     int i;
20     for (i = 0; i < k; ++i)
21         if (s[i] != t[i]) return 0;
22     return 1;
23 }
24 
25 int hash(int *s, int k)
26 {
27     int i;
28     unsigned int h = 0, g;
29     for (i = 0; i < k; ++i)
30     {
31         h = (h<<4)+s[i];
32         g = h&0xF0000000;
33         if (g) h^=g>>24;
34         h &= ~g;
35     }
36     return (h%MOD+MOD)%MOD;
37 }
38 
39 int main()
40 {
41     int n, k, i, j, ans = 0, t, x;
42     scanf("%d%d", &n, &k);
43     memset(sum[0], 0, sizeof(sum[0]));
44     memset(h, -1, sizeof(h));
45     h[0] = 0;
46     for (i = 1; i <= n; ++i)
47     {
48         scanf("%d", &a[i]);
49         for (j = 0; j < k; ++j)
50         {
51             sum[i][j] += (sum[i-1][j]+get(a[i], j));
52             c[i][j] = sum[i][j] - sum[i][0];
53         }
54         t = hash(c[i], k);
55         while (h[t] != -1)
56         {
57             x = h[t];
58             for (j = 0; j < k; ++j)
59                 if (c[i][j] != c[x][j]) break;
60             if (j >= k)    {ans = Max(ans, i-x);break;}
61             ++t;
62         }
63         if (h[t] == -1) h[t] = i;
64     }
65     printf("%d\n", ans);
66     
67     return 0;
68 }