@[saipubw](/space/show?uid=128307)
我没搞懂那个……大佬有说的详细点的教程吗
by 康师傅 @ 2019-02-05 02:35:56
@[康师傅](/space/show?uid=136822)
这题如果暴力比较字符就是n^4
但是可以利用类似dp的方式对每个矩阵算hash，时空复杂度下降为n^3，再滚动一下内存就是o(n^2)了，既不会超时也不会爆内存
by saipubw @ 2019-02-05 02:40:01
@[saipubw](/space/show?uid=128307)
没看明白hash……
by 康师傅 @ 2019-02-05 02:42:13
@[康师傅](/space/show?uid=136822)
hash实现方式可以看模板题
这题我算hash用的是
```c
hash[i][j][k] = hash[i-1][j][k] * base1 + hash[i-1][j + 1][k] * base2 + hash[i-1][j][k + 1] * base3 + map[j + i][k + i] * base4;
```
180度旋转把上面稍微改一下，比较两个的值就知道是不是相同的矩阵。
再滚动一下变成二维数组就可以ac了
by saipubw @ 2019-02-05 02:45:08
@[康师傅](/space/show?uid=136822)
https://www.luogu.org/problemnew/solution/P3370
这里的hash题解很详细了
by saipubw @ 2019-02-05 02:46:00
这里写ull 自然溢出hash就行
by saipubw @ 2019-02-05 02:47:39
@[saipubw](/space/show?uid=128307)
蟹蟹
by 康师傅 @ 2019-02-05 07:29:39