對于這些英文的題目，我們的首要任務是搞清楚題目的意思。題目大意：

說實話，我起初拿到這題的時候并不認為這題和哈希有半毛錢關系……

好吧，我們還是講題目吧。（正經臉）

1、我們把依次讀入的x轉化成一個二進制數c[i]，得到一個01矩陣a[n][k-1]。

2、我們可以對a數組進行前綴求和，得到c數組的前綴和數組sum[n][k-1]。

3、我們枚舉i和j(i>j)，判斷sum[i][l]-sum[j][l](0<=l<=k-1)是否等于sum[[i][0]-sum[j][0]，若等于，則ans=max(ans,i-j)。注意：是i-j，而不是i-j+1，因為sum數組是前綴和。

以上都是O(n^2)的正常思路，可惜n的最大值為100000，鐵定TLE。

接下來我將詳細闡述正解：hash

請觀察上述解法第3步的判斷，若sum[i]-sum[j]=sum[i][0]-sum[j][0]，則sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=……=sum[i][k-1]-sum[j][k-1]

由上述等式可得：sum[i][1]-sum[i][0]=sum[j][1]-sum[j][0],sum[i][2]-sum[i][0]=sum[j][2]-sum[j][0]……sum[i][k-1]-sum[i][0]=sum[j][k-1]-sum[j][0]

上述等式的變形是這道題的解題關鍵所在。經過上述對sum數組的操作后，我們可以得到一個新的數組：c[i][j]表示sum[i][j]-sum[i][0]

然后原問題就轉化成了求c數組中相同兩行的最遠距離，設k=hash(c[i])，在枚舉h[k]中的所有元素，更新ans。

小提示：記得在更新ans之前在h[0]中加入一個元素：0，即在c數組加上第0行：全都是0的一行。

附上AC代碼：

#include <cstdio>#include <vector>#define lyf 233333using namespace std;vector <int> h[lyf+1];int n,m,x,a[100010][31],sum[100010][31],c[100010][31],ans;int abs(int a){	return a>0?a:-a;}int hash(int x){	int ans=0;	for (int i=0; i<=m; ++i)		ans+=c[x][i]*i;	return abs(ans)%lyf;}bool pd(int i,int j){	for (int k=0; k<=m; ++k)		if (c[i][k]!=c[j][k]) return 0;	return 1; }int max(int a,int b){	return a>b?a:b;}int main(void){	scanf("%d%d",&n,&m);--m;	h[0].push_back(0);	for (int i=1; i<=n; ++i){		scanf("%d",&x);		for (int j=0; j<=m; ++j){			a[i][j]=x%2,x/=2;			sum[i][j]=sum[i-1][j]+a[i][j];			c[i][j]=sum[i][j]-sum[i][0];		}		int k=hash(i);		for (int j=0; j<h[k].size(); ++j)			if (pd(i,h[k][j])) ans=max(ans,abs(i-h[k][j]));		h[k].push_back(i);	}	PRintf("%d",ans);	return 0;}