自动搬运

查看原文

来自洛谷，原作者为

	平衡树森林 AFO

搬运于2025-08-24 21:34:48，当前版本为作者最后更新于2020-08-20 22:23:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我好像无意间搞出了二维哈希！

---

• 题目让我们求一个最大的旋转对称的正方形

• $n,m<=300$意味这我们最多能承受$n^3$的复杂度

怎么办呢？

我会暴力！

一个简单的思路：枚举每个正方形，然后判断这个正方形是否旋转对称

然后我们发现，单单是枚举每个正方形就已经有$n^3$的复杂度了，

别急，还有希望！ 假如我们能在$O(1)$的时间内判断旋转对称呢？

立马想到，假如我们有一种哈希，它能在$O(1)$的时间内获取任何一个矩阵的哈希值，那就好办了。咱们可以正着取那个正方形的哈希值，再把矩阵倒着再取一遍，判断是否一样即可。

可是我们没有二维哈希呀>.<，那就先从一维哈希入手，找点灵感：

一维哈希

一维哈希是这样的：对于序列

$$a_1,a_2,a_3......a_k$$

我们想要给每一个序列一个独一无二的哈希值H，这样我们只需要花费$O(1)$的时间去比较这个值，就能快速比较出两个数列是否相同了

• 一种简单的思想，讲所有数的和直接作为H。但这显然是不行的，反例太好举了

• 思想进阶一下：如果我们作为H的是所有数的平方和呢？仍然有反例，但明显要好得多

• 再深入想一下，二次不行，咱们还可以立方和，四次方，五次方...甚至可以用指数函数，总有一个不容易有反例吧！

但这种做法显然有一个致命的漏洞，就是我们完全不能决定序列的顺序。相反，如果是对于集合哈希，这个方法非常优秀，可咱们是数列啊！/

于是一位奆佬给出了一个解决方案：我们可以找一个比所有a都大的p，然后直接把序列当成一个p进制的大数，以此作为H。当然，这个数大到我们存不下来，但没关系，我们还能取模啊！把它对一个大质数取模，就能得到一个近乎不可能重复的哈希值了。同时我们也发现，对于两个相似的序列，只要它们稍稍有一点不同，所得的哈希值就千差万别。完美解决！

两种算法一个适用于集合，一个适用于序列，它们究竟差在哪呢？

仔细思考一下，会发现，序列中顺序非常重要。那么如果我把序列中的每一个元素变成一个二元组，第一元是数值，第二元是它的位置，会发生什么呢？奇妙的事情出现了：序列变成了二元组的集合！

原来序列的本质是集合！

回过来看看那个正确的哈希，根据位值原理，我们可以把它想象成，它首先把序列变成了 $p^1a_1,p^2a_2,p^3a_3...p^ka_k$，再求和（首项应该是从0开始的，但从1开始其实没什么影响）。

与我们的想法的区别在于，我们最初的想法在哈希时完全没有考虑顺序，而这个哈希在计算时先把位置与对应的值用计算“绑定”到了一起，于是哈希的结果就考虑到了顺序。

也就是说，对于序列的哈希关键在于我们要找一个二元函数$h(x,i)$，然后把序列的每个$a_i$变成$h(a_i,i)$，最终的哈希值就是所有$h$的和。这样哈希出来的值便可以兼顾元素的值与顺序

照这个思路，二维哈希就很容易了：

---

二维哈希

对于一个r行c列的矩阵

$$a_{1,1},a_{1,2}...a_{1,c}$$ $$a_{2,1},a_{2,2}...a_{2,c}$$ $$...$$ $$a_{r,1},a_{r,2}...a_{r,c}$$

我们可以找两个质数p,q，然后把i行j列元素变成$a_{i,j}*p^i*q^j$，然后矩阵的哈希值就是所有数的和，即

$$H=(\sum_{i,j<=r,c}a_{i,j}*p^i*q^j) \%mod$$

这样很明显，我们可以把哈希写成二维前缀和的形式了，做完了？

别急，还没完。思考一下，如果我们先用二维前缀和来预处理，那么计算一个中间的矩阵的哈希值时，首项的p和q的指数都不是从1开始的，也就是说，如果我们求的矩阵的左上角为$(x,y)$，那么实际上求得的哈希值是原来的$p^{x-1}*q^{y-1}$倍。

怎么办呢？除掉？显然不可行，因为在模意义下除法可不好做。我还会滑动窗口滑动窗口太麻烦了，有没有简单的解决方法呢？

有的！除法不行，但是我们可以乘啊！我们重新定义哈希函数：

$$H=(\sum_{i,j<=r,c}a_{i,j}*p^{i+n}*q^{j+m}) \%mod$$

但处理二维前缀和时每个数仍然变成$a_{i,j}*p^i*q^j$

这样二维前缀和算出来的值就比实际的哈希值少了$p^{n-x}*q^{m-j}$倍，咱们可以直接乘上去

二维哈希，完成！

---

回归本题，我们只需要正这做一遍哈希，倒过来再做一遍，就可以在$O(1)$的时间里判断一个正方形是否为旋转对称了

时间复杂度$O(n^3)$

而事实上，这个算法的时间复杂度显然是还能降低的。我们只需要先枚举正方形中心点，再向外二分，就能把时间复杂度降到$O(n^2log_2n)$

但是朴素算法能过，咱何必呢

上代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define FOR  for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++)
#define FOR2 for(LL i=n;i>=1;i--)for(LL j=m;j>=1;j--)
using namespace std;

inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const LL maxn=300+10;
const LL A=10007,B=10009;
const LL MOD=1e9+9;
LL a[maxn][maxn];
LL X1[maxn],X2[maxn];
LL h1[maxn][maxn],h2[maxn][maxn];
LL n=read(),m=read();

LL hash1(LL a,LL b,LL c,LL d)
{
	LL ans=(h1[c][d]-h1[a-1][d]-h1[c][b-1]+h1[a-1][b-1]+MOD)%MOD;
	return ans*X1[n-a]%MOD*X2[m-b]%MOD;
}

LL hash2(LL a,LL b,LL c,LL d)
{
	LL ans=(h2[a][b]-h2[c+1][b]-h2[a][d+1]+h2[c+1][d+1]+MOD)%MOD;
	return ans*X1[c-1]%MOD*X2[d-1]%MOD;
}

int main()
{
	FOR
	{
		char ch;cin>>ch;
		if (ch=='1') a[i][j]=1;
	}
	X1[0]=X2[0]=1;
	for (LL i=1;i<=300;i++) X1[i]=X1[i-1]*A%MOD,X2[i]=X2[i-1]*B%MOD;
	FOR h1[i][j]=X1[i]*X2[j]*a[i][j]%MOD;
	FOR h2[i][j]=X1[n-i+1]*X2[m-j+1]*a[i][j]%MOD;
	FOR h1[i][j]=h1[i-1][j]+h1[i][j-1]-h1[i-1][j-1]+h1[i][j];
	FOR2 h2[i][j]=h2[i+1][j]+h2[i][j+1]-h2[i+1][j+1]+h2[i][j];
	LL ans=0;
	FOR for (LL k=1;k+i<=n && k+j<=m;k++)
		if (hash1(i,j,i+k,j+k)==hash2(i,j,i+k,j+k)) ans=max(ans,k+1);
	if (ans==0) cout<<-1<<endl; else cout<<ans<<endl;
	return 0;
}

ps.这种哈希法还真是我自己想的，如果本来就有相关文章，各位可以在评论区里说一声~ STO STO

求个赞>.<

~~