排排站（codevs1247)-哈希练习 —— By litble

题目大意

就是说，用一个二进制数描述一个奶牛，如果该位是 1，表示奶牛有这个特征，如果为 0，表示没有。所有奶牛站成一排，你要找出其中一串奶牛，对于每一个特征，这一串奶牛中拥有该特征的奶牛数相同，求这一串奶牛最长的长度。

输入格式

n 表示奶牛数量（n<=100000)
k 表示特征数量（n<=30)
然后有 n 个数，用一个十进制的数描述这个奶牛的特征（你要转换为二进制数）

输出格式

答案，最长的那一串符号要求的奶牛的长度

思路

恩，首先我想，如果用 f[i][j] 来表示前 i 个奶牛中拥有 j 特征的奶牛数量，这样的话，只要枚举起点 s 和终点 t，假如 f[s-1][1]-f[t][1]=f[s-1][2]-f[t][2]=…=f[s-1][k]-f[t][k]. 为什么是 s-1 呢，是因为 s 处和 t 处的奶牛都要考虑。就像你求从 6 到 10 有几个数，答案不是 4 个而是 5 个一样，因为 6 和 10 都要包括。
然后我枚举起点和终点，然后绝对 TLE 啊有木有！！！！
于是我搜了题解…… 惊奇地发现假如 f[s-1][1]-f[t][1]=f[s-1][2]-f[t][2]=…=f[s-1][k]-f[t][k] 的话，那么 f[t][2]-f[t][1]=f[s-1][2]-f[s-1][1],f[t][3]-f[t][1]=f[s-1][3]-f[s-1][1]… 以此类推，把前一串式子变形就可以得到了。我们让 ff[i][j]=f[i][j]-f[i][1]。
啊！这样的话，我们只要哈希对于每个 i 值的 f[i][2…k]-f[i][1] 就可以了！
不过，要怎么写哈希呢？
如果你直接取模的话，百分之一百二会重复有木有！！！！
所以我们要用链表哈希。
然后就神奇地过了。
代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,ans,mod=999997,tot;
int a[N][32],b[N][32],bin[32];
int h[1000000],ne[N],q[N];
int ok(int x,int y){
    for(int i=1;i<=m;++i)
        if(b[x][i]!=b[y][i])return 0;
    return 1;
}
void add(int x,int wz){
    for(int i=h[x];i!=-1;i=ne[i])
        if(ok(wz,q[i])){ans=max(ans,wz-q[i]);return;}
    ++tot,q[tot]=wz,ne[tot]=h[x],h[x]=tot;
}
int main()
{
    int i,j,x,kl;
    memset(h,-1,sizeof(h));
    add(0,0);
    scanf("%d%d",&n,&m);
    bin[1]=1;for(i=2;i<=m;++i)bin[i]=bin[i-1]<<1;
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        kl=0;
        for(j=1;j<=m;++j){
            if((x&bin[j]))a[i][j]=1;
            a[i][j]=a[i][j]+a[i-1][j];
        }
        for(j=1;j<=m;++j){
            b[i][j]=a[i][j]-a[i][1];
            kl=kl%mod+b[i][j]<<2;
        }
        if(kl<0)kl=-kl;
        add(kl%mod,i);
    }
    printf("%d",ans);
    return 0;
}