8707: 学习系列 —— 字符串双模数哈希
[Creator : ]
Description
【背景】
对字符串的哈希存储，我们可以选择 STL 的 unordered_map。有时候，我们需要自己对字符串计算哈希值。我们当然可以遍历这个字符串，将字符串所有字符来计算哈希值，但是这样做的算法时间复杂度太高。我们承受不起。
单次计算一个字符串的哈希值复杂度是
$O(n)$，其中 $n$ 为串长，与暴力匹配没有区别。如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。 一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个
$b$ 进制的数对 $M$ 取模的结果，这样的话每次就能快速求出子串的哈希了： 令 $f_i(s)$ 表示 $f(s[1..i])$，即原串长度为 $i$ 的前缀的哈希值。那么按照定义有
$f_i(s)=s[1]\cdot b^{i-1}+s[2]\cdot b^{i-2}+\cdots+s[i-1]\cdot b^{1}+s[i]\cdot b^{0}$
现在我们使用类似前缀和的方式快速求出 $f(s[l..r])$，按照定义有字符串 $s[l..r]$ 的哈希值为
$s[l..r]=s[l]\cdot b^{r-l}+s[l+1]\cdot b^{r-l-1}+\cdots+s[r-1]\cdot b^{1}+s[r]\cdot b^{0}$
对比观察上述两个式子，我们发现 $f(s[l..r])=f_r(s)-f_{l-1}(s)\times b^{r-l+1}$
成立（可以手动代入验证一下），因此我们用这个式子就可以快速得到子串的哈希值。其中 $b^{r-l+1}$ 可以 $O(n)$ 的预处理出来然后 $O(1)$ 的回答每次询问，当然也可以使用快速木 $O(logn)$ 的回答出。 【要求】
使用上面的算法。给定一个长度为 $n$ 的字符串，两个的 BASE，请计算该字符串对应 $s[l..r]$ 字符串的哈希值。
Input
第一行包括三个整数 $n,m$，其中 $n$ 表示字符串 $s$ 的长度，$m$ 表示每个字符串的长度。
第二行包括两个数，$BASE_1, MO_1$，其中 $BASE_1$ 表示计算哈希的指数，$MO_1$ 表示模数。
第三行包括两个数，$BASE_2, MO_2$，其中 $BASE_2$ 表示计算哈希的指数，$MO_2$ 表示模数。
第四行包括一个长度为 $n$ 的字符串。可能包含空格。
P.S.
OI 中有些题目会卡单模数哈希。所以我们一般都直接使用双模数哈希。
第二行包括两个数，$BASE_1, MO_1$，其中 $BASE_1$ 表示计算哈希的指数，$MO_1$ 表示模数。
第三行包括两个数，$BASE_2, MO_2$，其中 $BASE_2$ 表示计算哈希的指数，$MO_2$ 表示模数。
第四行包括一个长度为 $n$ 的字符串。可能包含空格。
P.S.
OI 中有些题目会卡单模数哈希。所以我们一般都直接使用双模数哈希。
Output
一共有 $n-m+1$ 行。每行两个无符号整数。
第 $i$ 行第一个数字表示从字符 $i-1$ 开始，长度为 $m$ 的子字符串使用 $BASE_1,MO_1$ 计算出的哈希值。第二个数字表示从字符 $i-1$ 开始，长度为 $m$ 的子字符串使用 $BASE_2,MO_2$ 计算出的哈希值。
第 $i$ 行第一个数字表示从字符 $i-1$ 开始，长度为 $m$ 的子字符串使用 $BASE_1,MO_1$ 计算出的哈希值。第二个数字表示从字符 $i-1$ 开始，长度为 $m$ 的子字符串使用 $BASE_2,MO_2$ 计算出的哈希值。
Constraints
$1\leq m \leq n \leq 10^6$
Sample 1 Input
13 5
133 1000000007
233 1000000009
1231234123123
Sample 1 Output
450675780 52726280
765893894 12562767
74107157 934614119
450676178 52726978
765946827 12725400
81147245 972507607
387007875 881909610
450675780 52726280
765893894 12562767
Sample 2 Input
13 5
133 1000000007
1313 1000000017
1231234123123
Sample 2 Output
450675780 650609097
765893894 979796173
74107157 523441367
450676178 650613035
765946827 984966766
81147245 312429856
387007875 592503801
450675780 650609097
765893894 979796173
Sample 3 Input
43 5
233 1000000007
1373 1000000019
12a 31 23x412d 31Z23wM dIKJ@xkj*#xkljuiere
Sample 3 Output
55219904 449681800
593509883 687710815
295222507 915309761
961239868 855732636
933636983 161449299
824984758 772029680
948719615 271341641
16418046 792628419
832825449 967177335
335897477 36602055
881921316 906729386
55382771 455337187
631457894 452557014
137109065 49147164
961253382 855812270
936785745 270786781
558646296 892389615
891858428 525529286
16369565 790777598
821529426 426000190
703924112 396060
351978296 782131663
582370353 726856115
657040617 213989342
105304214 184118421
986716029 999620195
915964313 511069759
150666117 317566235
34703549 499557096
703736670 543988683
946523378 169578004
235677528 689957942
679097140 690474558
34827121 503415308
732528931 841313649
655120136 396748564
899019456 422666043
167263772 179828870
749823051 315839882