题目链接：
https://vjudge.net/problem/POJ-3274
题目大意：
给定多头牛的属性，每头牛的属性由一个非负数表示，该数的二进制表示不会超过K位，它的二进制表示的每一位若为1则表示该牛有对应的第i种属性，若为0则表示没有该属性。
对于给定的牛的顺序，要求输出某一段子序列的长度，这个子序列中的牛的K个属性对应相加以后全部相等。
假设n=3, k = 3
输入的3个数变成的二进制分别为(a1, a2, a3), (b1, b2, b3), (c1, c2, c3)
设sum(i)为从第1个数到第i个数的属性和的序列
若从第2个数到第3个数的序列满足条件，则说明b1+c1 = b2+c2 = b3+c3，即sum(3)-sum(2)的序列每一位都相等
推广一下，若sum(i) = (a, b, c)，sum(j) = (d, e, f)，且i到j这个子序列满足条件，则说明(d, e, f) – (a, b, c) = (x, x, x)，即(d, e, f) = (a + x, b + x, c + x)。每个序列中的数都减去序列中的最后一个数，得到(d – f, e – f, 0) = (a – c, b – c, 0)。因此只要判断两个完全转换过后的序列是否相同，就可以知道它们之间的原序列是否满足条件了。
所以解题的第一步是把原来的数转换为二进制序列，第二步是把二进制序列转换成sum序列，即逐步叠加，第三步是把每个sum序列都减去该序列的最后一个数，最后一步是把这些序列进行哈希，计算它们的最大差距。
有一点要注意，如果从第1个数到第i个数这段序列满足条件，即sum(i) – sum(0) = (x, x, x)，则说明sum(i)的各个位都是相同的，因此需要在第三步之前先做这个判断，把符合条件的序列找出来，更新一下答案。所以在hash的时候先存入hash(0)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<cmath>
using namespace std;
const int maxn = + ;
const int mod = ;
int num[maxn][];
int n, k;
int maxlen;
struct hashtable
{
int x;
hashtable * next;
hashtable(){next = ;}
};
hashtable * Hash[mod]; bool Equal(int i, int j)
{
for(int c = ; c < k; c++)
if(num[i][c] != num[j][c])return false;
return true;
}
void Hash_Insert(int i)
//根据关键字key找hash位置, 找到位置后存i表示第i行
{
int key = ;
for(int j = ; j < k; j++)
key += j * num[i][j];
key = abs(key) % mod;
if(!Hash[key])//链表的第一个key
{
hashtable* p = new hashtable;
p -> x = i;
Hash[key] = p;
}
else//产生冲突
{
hashtable * p = Hash[key];
if(Equal(p->x, i))//如果和第i行相等
{
int dist = i - (p -> x);
maxlen = max(maxlen, dist);
}
else
{
while(p->next)//判断p->next是否存在，之后直接判断p->next存的行数和当前行数比较
{
if(Equal(p->next->x, i))
{
int dist = i - (p -> next -> x);
maxlen = max(maxlen, dist);
return;//不用存储i，直接返回，因为已经有和i一样的
}
p = p->next;
}
//地址冲突但是和每个冲突的都不相同
hashtable* temp = new hashtable;
temp->x = i;
p->next = temp;
}
}
return;
}
int main()
{
scanf("%d%d", &n, &k);
int x;
for(int i = ; i <= n; i++)
{
scanf("%d", &x);
for(int j = ; j < k; j++)
if(x & ( << j))num[i][j] = ;
for(int j = ; j < k; j++)
num[i][j] += num[i - ][j];
}
for(int i = ; i <= n; i++)
{
for(int j = ; j < k; j++)
num[i][j] -= num[i][];
}
for(int i = ; i <= n; i++)Hash_Insert(i);//从第0行开始
cout<<maxlen<<endl;
}
