尝试使用哈希。首先，我们可以发现，我们去枚举最终答案矩形的长和宽。然后我们会发现宽是关于长单调减少的。那么我们就可以写一个双指针，每次检查对当前的 \(x,y\)，是否存在长为 \(x\)，宽为 \(y\) 的相同子阵。因为是双指针，所以枚举的复杂度是 \(O(n+m)\) 的。
然后考虑匹配。我们发现，我们可以使用哈希，具体的，我们先预处理矩阵哈希表，然后在当前矩阵中枚举左上角的位置，通过当前的 \(x,y\) \(O(1)\) 求出子矩阵哈希值，存入 map 中。然后对第二个矩阵如法炮制，只是计算出哈希值之后在 map 中查找是否有相同的哈希值。
对于如何计算矩阵哈希，利用二维前缀和计算矩阵哈希是有点困难（但并非不可能的）。但是在这道题中，我们很明显可以有更优的方法。我们只是计算每一行的哈希值，在枚举左上角的时候先枚举列数，然后再枚举行。每次行编号增加只需要增加多出来的一行在当前列区间的哈希值和原先行在当前列区间的哈希值。区间哈希是 \(O(1)\) 的，总复杂度就是 \(O(nm(n+m)\log (nm))\)，如果使用哈希表代替 map，甚至可以做到 \(O(nm(n+m))\)。
https://codeforces.com/gym/100213/submission/4003803 by HTTPs: sillyboy, ddldyj237, technolt
标签：map,ASC8,Money,矩阵,Counterfelt,枚举,哈希,我们,nm From： https://www.cnblogs.com/jucason-xu/p/17437028.html