这道题目就是一个二维hash模板
讲一下二维哈希
二维的数据结构一般都是先对一个既定的行做列（一维）上的操作，然后再把若干列当成一维处理行（数组指针指向一个二维数组就可以这么理解）
设\(hash[i][j]\)表示前\(i\)行前\(j\)列的矩阵的hash值
我们先对列做hash（设进制数为\(base_1\)）
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
hash[i][j]=hash[i][j-1]*base1+a[i][j];
然后再对行做hash（设进制数为\(base_2\)）
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
hash[i][j]+=hash[i-1][j]*base2;
我们求其中一个子矩阵（假设顶点为\((i,j)\)，大小为\(n\times m\)）的hash的时候，就利用类似二维前缀和的方法即可
\[hash[i][j]-hash[i-n][j] \cdot base_1^n - hash[i][j-m] \cdot base_2^m + hash[i-n][j-m] \cdot base_1^n*base_2^m \]可以想一下为什么上式是对的
然后这道题目就很easy了
标签：hash,cdot,矩阵,int,二维,base From： https://www.cnblogs.com/dingxingdi/p/17968642