[省选] [线段树] HLOI2016Day1 字符串问题

问题描述 Description

我们知道，哈希（hash）算法被广泛应用于字符串处理领域之中。现有如下哈希函数： f(s,l,r)=∏i−lrord(si)modp $$f(s,l,r)=/<a href="http://pr.VeVb.com/">PR</a>od_{i-l}^r ord(s_i) /mod p$$ 公式中，ord$ord$代表的是字符的ascii码，mod$/text{mod}$代表的是求余操作，∏$/prod$则是求积操作，意为求l$l$到r$r$之间所有字符的积。 现在给定一个长度为N$N$的字符串，并给出p$p$，之后会有若干组询问，每次询问这个字符串相对于那个区间的子串的哈希值。

输入 Input

输入文件包括若干行，其中第一行是一个字符串 ，数据保证其中只会出现小写英文字母。 第二行是一个整数p$p$。 第三行是一个整数m$m$，表示询问的次数。 接下来的m$m$行，每行有两个整数l,r(1≤l≤r≤n)$l,r(1≤l≤r≤n)$，表示询问从第l$l$位到第r$r$位的哈希值。

输出 Output

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

样例输入 Sample Input

efqzvcowdormnslhjzznubn 56 4 17 18 7 20 14 16 15 23

样例输出 Sample Output

52 0 40 0

限制 Limits

对于30%$30/%$的数据，1≤N≤100，1≤m≤10$1≤N≤100 ，1≤m≤10$； 对于70%$70/%$的数据，1≤N≤105，1≤m≤104$1≤N≤10^5 ，1≤m≤10^4$； 对于100%$100/%$的数据，1≤N≤105，1≤m≤105$1≤N≤10^5 ，1≤m≤10^5$。 Time Limit : 1s$1s$ & Memory Limit : 128MB$128MB$

黑历史题，只有查询的线段树 Code 只有查询？先求前缀积，再求个逆元，搞一搞就好了…… 但是并不知道p$p$有多大，题中也没说，题解说可以写也是一种优化方法吧。 时间O(nlogn+Tlogn)$O(nlogn+Tlogn)$