哈希hash

hash其实就是把一个字符串或数字映射成一个值域范围更小的数字，很简单对吧
那末总么实现呢？
D板子：https://www.luogu.com.cn/problem/P3370
我们首先固定一个base，然后要把字符串转化成base进制的数（base要包含值域且通常为大质数），并用unsigned long long 存（相当于对\(2^{64}\)取模）。
(eg:\(h\)₁\(\times\)\(P^{5}\)+\(h\)₂\(\times\)\(P^{4}\)+\(h\)₃\(\times\)\(P^{3}\)+\(h\)₄\(\times\)\(P^{2}\)+\(h\)₅\(\times\)\(P^{1}\)+\(h\)₆\(\times\)\(P^{0}\))
这是一维哈希。
下面是一维哈希的前缀和：
还是上面那个例子：\(h\)₁\(\times\)\(P^{5}\)+\(h\)₂\(\times\)\(P^{4}\)+\(h\)₃\(\times\)\(P^{3}\)+\(h\)₄\(\times\)\(P^{2}\)+\(h\)₅\(\times\)\(P^{1}\)+\(h\)₆\(\times\)\(P^{0}\)
\(sum[1]=\)\(h\)₁\(\times\)\(P^{0}\),\(sum[2]=\)\(h\)₁\(\times\)\(P^{1}\)+\(h\)₂\(\times\)\(P^{0}\)
\(......\)
\(sum[6]=\)\(h\)₁\(\times\)\(P^{5}\)+\(h\)₂\(\times\)\(P^{4}\)+\(h\)₃\(\times\)\(P^{3}\)+\(h\)₄\(\times\)\(P^{2}\)+\(h\)₅\(\times\)\(P^{1}\)+\(h\)₆\(\times\)\(P^{0}\)
那末3~6的哈希值\(=\)\(sum[6]-sum[2]\times(6-3+1)\)
故l-r的哈希值\(sum[r]-sum[l-1]\times(r-l+1)\)
下面是二维哈希：
一维哈希能把一个串或序列表示成一个数字，而二维的能把一个矩阵用一个数表示。
先把每行做个哈希，再按列对每行的hash再做哈希
（eg：http://noip.ybtoj.com.cn/contest/875/problem/3）
哈希表：
其实手写用处不大
专业的讲解：https://oi-wiki.org/ds/hash/
很多时候可以用map或unordered_map实现，
可以把每个要插入的元素放到这里跑一边：

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

注意 ：

1. 枚举正方形时可枚举正方形中心，再二分正方形边长。