「HLOI2016」字符串

Posted on In
HLOI2016 Day1 T1

题目描述

我们知道，哈希 (hash) 算法被广泛应用于字符串处理领域之中。现有如下哈希函数：

公式中， 代表的是字符的 ASCII 码， 代表的是求余操作， 则是求积操作，意为求 到 之间所有字符的 ASCII 码的积。

现在给定一个长度为 的字符串，并给出 ，之后会有若干组询问，每次询问这个字符串相对于那个区间的子串的哈希值。

输入

输入包括若干行，其中第一行是一个字符串，数据保证其中只会出现小写英文字母；

第二行是一个整数 ；

第三行是一个整数 ，表示询问的次数；

接下来的 行，每行有两个整数 ，表示询问从第 位到第 位的哈希值。

输出

输出包括 行，依次给出输入文件中相应的询问对应的答案。

样例输入

1
2
3
4
5
6
7
efqzvcowdormnslhjzznubn
56
4
17 18
7 20
14 16
15 23

样例输出

1
2
3
4
52
0
40
0

数据范围及约定

对于 的数据，；

对于 的数据，；

对于 的数据，。

时间与空间限制

时间限制：，空间限制：。

题解

黑历史题，只有查询的线段树……

只有查询？先求前缀积，再求个逆元，搞一搞就好了……

但是并不知道 有多大，题中也没说，题解说可以写也是一种优化方法吧。

时间复杂度为 ，空间复杂度为 。

代码见这里。