题解 P2177 【内存杀手】

· · 题解

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

怎么办呢？

我会暴力！

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

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

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

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

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

一维哈希

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

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

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

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

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

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

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

原来序列的本质是集合！

回过来看看那个正确的哈希，根据位值原理，我们可以把它想象成，它首先把序列变成了

与我们的想法的区别在于，我们最初的想法在哈希时完全没有考虑顺序，而这个哈希在计算时先把位置与对应的值用计算“绑定”到了一起，于是哈希的结果就考虑到了顺序。 也就是说，对于序列的哈希关键在于我们要找一个二元函数$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

求个赞>.<

~~