poj 3274ハッシュ

http://poj.org/problem?id=3274
Description
Farmer John's N cows（1≦ N ≦100,000）share many simillares.In fact，FJ has been able to narrow down the list of feature shared by his cows to a list of only K ディfferent feat ures(1≦ K ≤30).For example，cows exhibiting feature(zhi 1 might have spots，cows exhibiting feature，and so.
FJ has Evern devised a concise way to describe each cow in terms of its「feature ID」、a single K-bitintegerwhose binaryrepresentatit tellss the set of feaature s exhibited bythe cow.As exple、suppe=appeeeexxple-3.aaaaaaatetetetes=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaates=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaates（reading right to left）but not feature 2.More generaally、we find a 1 in the 2^(i-1)place if a cow exhibits feature i.
Always the sensitive fellow，FJ lind up cows 1.N in a long row and noticed that certain ranges of cows are somewhat「balanced」in terms of the feature s the exhibit.A contigous range of cows i.j is balanced if each of the K possible feature s is exhibited by the same number of cows in the range.FJ is curious as to the size of the larget balanced range of cows.See if you can determine it.
Input
Line 1：Two space-separated integers、 
N and 
K. 
Lines 2.
N+1:Line 
i＋1 contains a single 
K-bit integer specifying the feature s present in cow 
i.The least-significant bit of this integer is 1 if the cow exhibits feature刋1，and the most-significant bit is 1 if the cow exhibits feature
K.
Output
Line 1:A single integer giving the size of the larget st contigous balanced group of cows.
Sample Input

7 3
7
6
7
2
1
4
2

Sample Output

4

乳牛1頭につき「feature ID」がありますが、この数をKビットのバイナリと表現しています。対応するビットは1でそれぞれの特徴を表しています。このようにn頭の乳牛は1列に並んでいます。一番長い連続区間を求めて、中の乳牛のK個の特徴個数がバランスを取ります。
sum[i][j]で前i頭乳牛のj番目の特徴個数の総和を表すと、区間[a+1,b]には、
sum[b][1]-sum[a]=sum[b]、[2]-sum[a][2] = sum[b][j]-sum[a][j]   (1<=j<=K)
式に変換する:
sum[b][1]-sum[b]=sum[a][1]-sum[2]
sum[b]-sum[b]=sum[a]、[1]-sum[a][j]   (1<=j<=K)
c[i][j]=sum[i]-sum[i]、[1]（1<=j==K）を令すると
条件はc[a]==c[b]に変換できます。
これで私達は求めているc[i][j]（1<= i<=N，1<=j==K)をもとに、配列c[i](1==i==N)hashに対して、ハッシュ法(ファスナー法)で解いても良いです。インターネットから摘出する）
ハッシュの結果は、ハッシュ値が同じシーケンスを再比較することで、時間の複雑さを低減する。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int hashseed=99983;
int n,k;
int sum[maxn][35],c[maxn][35];
int head[hashseed+2],next[maxn];

int hash(int v[])
{
    int h=0;
    for(int i=1; i<=k; i++)
    {
        h=(h<<2)+(v[i]>>4)^(v[i]<<10);
    }
    h=(h+hashseed)%hashseed;
    return h;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        memset(sum,0,sizeof(sum));
        for(int i=1; i<=n; i++)
        {
            int cnt;
            scanf("%d",&cnt);
            for(int j=1; j<=k; j++)
            {
                sum[i][j]=sum[i-1][j]+cnt%2;
                cnt/=2;
            }
        }
        int maxx=0;
        memset(head,-1,sizeof(head));
        for(int i=0; i<=n; i++)///    0  
        {
            for(int j=1; j<=k; j++)
            {
                c[i][j]=sum[i][j]-sum[i][1];
            }
            int h=hash(c[i]);
            bool flag=0;
            for(int p=head[h]; p!=-1; p=next[p])
            {
                int j;
                for(j=1; j<=k; j++)
                {
                    if(c[i][j]!=c[p][j])
                        break;
                }
                if(j>k)
                {
                    maxx=max(maxx,i-p);
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            {
                next[i]=head[h];
                head[h]=i;
            }
        }
        printf("%d
",maxx);
    }
    return 0;
}