字符串前缀哈希法
预处理所有前缀的哈希，且 h[0] = 0（h[0]不应被占用）
如何定义前缀的哈希值呢？
将字符串看成P进制数,（由于该数字可能很大），所以取模
$$“A B C D” => “1 2 3 4” => (1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p^0) % Q$$

在使用该哈希方法时，需要注意：
（1）不能映射成数字0
（2）人品足够好，不存在冲突，经验值：
$$P = 131 或 13331$$$$Q = 2^{64} $$
如何求L-R的哈希值呢？

补充一些小细节：
unsigned long long存储 就可以省去取模的操作

附上y总模板

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}