二维哈希的介绍
lijinmo
·
·
题解
二维哈希
二维哈希可以快速地比较两个矩形是否相同。在一些矩形题中很有用。
准备
- 两个质数 p1,p2。其中 p1 是行间移动要乘的，p2 是列间移动要乘的。
-
- 一个二维哈希数组，其中 ha_{i,j} 代表从 (1,1) 到 (i,j) 形成的矩形的哈希值。
- 模数。或者像我一样使用自然溢出（
unsigned long long）。
处理哈希数组
和二维前缀和类似的，有 ha_{i,j}=ha_{i-1,j} \times p1 + ha{i,j-1} \times p2 - ha_{i-1,j-1} \times p1 \times p2+z_{i,j}。
同理，$ha_{i,j-1} \times p2$ 因为是从上一列推过来，所以要乘 $p2$。
$ha_{i-1,j-1} \times p1 \times p2$ 则是因为前两项重复计算了左上角 $(1,1)$，右下角 $(i-1,j-1)$ 的矩形，所以要把它加起来，由于移动了一行一列，所以要乘 $p1 \times p2$。
最后的 $z_{i,j}$ 就表示当前点 $(i,j)$ 的字符对应的值，一般来讲这个值只要小于 $p1$ 和 $p2$ 即可。
:::success[参考实现]
```cpp
void hx()
{
cf1[0]=cf2[0]=1;
for(int i=1;i<N;i++)
{
cf1[i]=cf1[i-1]*p1;
cf2[i]=cf2[i-1]*p2;
}
for(int i=1;i<=2*n;i++)
{
for(int j=1;j<=2*m;j++)
{
ha[i][j]=ha[i-1][j]*p1+ha[i][j-1]*p2-ha[i-1][j-1]*p1*p2+d(c[i][j]);
}
}
}
```
:::
### 查询矩形哈希值
这个也和二维前缀和类似，对于一个左上角为 $(i,j)$，右下角为 $(x,y)$ 的矩形，它的哈希值为 $ha_{x,y}-ha_{i-1,y} \times p1^{x-i+1}-ha_{x,j-1} \times p2^{y-j+1}+ha_{i-1,j-1} \times p1^{x-i+1} \times p2^{y-j+1}$。
这个式子的原理就是把大矩形中不在查询范围内的减掉。$ha_{i-1,y}$ 因为移动了 $x-i+1$ 行，所以要乘 $p1^{x-i+1}$。$ha_{x,j-1}$ 因为移动了 $y-j+1$ 列，所以要乘 $p2^{y-j+1}$。最后发现减掉了两个左上角 $(1,1)$，右下角 $(i-1,j-1)$ 的矩形，所以要加回来。
:::success[参考实现]
```cpp
ull query(int i,int j,int x,int y)
{
return ha[x][y]-ha[i-1][y]*cf1[x-i+1]-ha[x][j-1]*cf2[y-j+1]+ha[i-1][j-1]*cf1[x-i+1]*cf2[y-j+1];
}
```
:::
## 本题解析
### 题意简化
给定一个大小为 $2n \times 2m$ 的矩形，要求出字典序最小的大小为 $n \times m$ 的矩形。
这个 $2n \times 2m$ 的矩形分成四块大小为 $n \times m$ 的矩形后，四块矩形的面积相等。
一个矩形的字典序就是把这个矩形逐行拆开，在按行的顺序拼在一起。
### 解析
很容易想到，可以枚举所有的 $n \times m$ 个矩形，每次比较当前答案是否比前面的最优解最优。如果更优，就更新最优解。
那接下来问题就是，如何比较两个矩形的字典序大小呢？首先，由于两个矩形前面相同的部分肯定对字典序大小没有贡献，所以我们用两次二分，第一次先找出两个矩形前面相同到第几行，第二次再找出相等的行的下一行前面相同到第几列，再判断两个矩形最后相等的字符的下一个位置即可。
每次二分的查询使用二维哈希可以做到 $\mathcal{O}(1)$。
时间复杂度 $\mathcal{O}(nm(\log n + \log m))$。
:::success[参考代码]
```cpp
#include<iostream>
#define ull unsigned long long
using namespace std;
const int N=2005;
const int p1=23,p2=13;
int n,m;
char c[N][N];
ull ha[N][N];
ull cf1[N],cf2[N];
int d(char c)
{
if(c=='*') return 1;
return 2;
}
void hx()
{
cf1[0]=cf2[0]=1;
for(int i=1;i<N;i++)
{
cf1[i]=cf1[i-1]*p1;
cf2[i]=cf2[i-1]*p2;
}
for(int i=1;i<=2*n;i++)
{
for(int j=1;j<=2*m;j++)
{
ha[i][j]=ha[i-1][j]*p1+ha[i][j-1]*p2-ha[i-1][j-1]*p1*p2+d(c[i][j]);
}
}
}
ull query(int i,int j,int x,int y)
{
return ha[x][y]-ha[i-1][y]*cf1[x-i+1]-ha[x][j-1]*cf2[y-j+1]+ha[i-1][j-1]*cf1[x-i+1]*cf2[y-j+1];
}
bool cmp(int i,int j,int x,int y)
{
int l=1,r=n,be=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(query(i,j,i+mid-1,j+m-1)==query(x,y,x+mid-1,y+m-1))
{
l=mid+1;
be=mid;
}
else
{
r=mid-1;
}
}
if(be==n) return 0;
l=1,r=m;
int b=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(query(i+be,j,i+be,j+mid-1)==query(x+be,y,x+be,y+mid-1))
{
l=mid+1;
b=mid;
}
else
{
r=mid-1;
}
}
return c[i+be][j+b]<c[x+be][y+b];
}
long long read()
{
long long out=0,fh=1;
char cc=getchar();
if(cc=='-') fh=-1;
while(cc>'9' || cc<'0') cc=getchar();
while(cc>='0' && cc<='9')
{
out=out*10+cc-'0';
cc=getchar();
}
return out*fh;
}
void write(long long x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x==0)
{
putchar('0');
return ;
}
long long num=0;
char c[40];
while(x)
{
c[++num]=(x%10)+48;
x/=10;
}
while(num)
{
putchar(c[num--]);
}
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c[i][j]=getchar();
while(c[i][j]!='.' && c[i][j]!='*') c[i][j]=getchar();
c[i+n][j]=c[i][j];
c[i][j+m]=c[i][j];
c[i+n][j+m]=c[i][j];
}
}
hx();
int x=1,y=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(cmp(i,j,x,y))
{
x=i;
y=j;
}
}
}
for(int i=x;i<=x+n-1;i++)
{
for(int j=y;j<=y+m-1;j++)
{
putchar(c[i][j]);
}
putchar('\n');
}
return 0;
}
```
:::