problem Description

度熊手上有一本字段存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串。现在麻烦来了，他忘记了原来的字符串是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到：

\(H(s)=\prod_{i=1}^{i\leq len(s)}(s_{i}-28)(mod 9973)\)

\(S_{i}\)代表S[i]字符的ASCII码。

请版主度熊计算大字符串中任意一段的哈希值是多少。

Input

多组测试数据，每组测试数据第一行是一个正整数N，代表询问的次数，第二行一个字符串，代表题目中的大字符串，接下来N行，每行包含两个正整数a和b，代表询问的起始位置以及终止位置。

\(1\leq N\leq 1,000\)

\(1\leq len(string) \leq 100,000\)

\(1\leq a,b\leq len(string)\)

Output

对于每一个询问，输出一个整数值，代表大字符串从 a 位到 b 位的子串的哈希值。

Sample Input

2
ACMlove2015
1 11
8 10
1
testMessage
1 1

Sample Output

6891
9240
88

题解

#include<iostream>
#include<cstring>
using namespace std;
#define MOD 9973 //要%的数 
int inv[10000];//存放逆元的数组 
int pre[100005];//存放前缀积 
char s[100005];//存放字符串
//快速幂，因为费马小定理要求一个数的(mod-2)次方
//a存放底数，b存放幂指数 
int quickPow(int a,int b){
    int r=1;//存放答案
    //不断迭代 
    while(b){
        //判断b是不是奇数 
        if(b&1){
            //b如果是奇数，将结果乘一个底数，同时结果模一下，防止数据过大 
            r=r*a%MOD;
        }
        b>>=1;//b右移一位，相当于除以2 
        a=a*a%MOD;//底数增大一倍 
    }
    return r;
}

int main(){
    int N,i,j,k;
    inv[1]=1;//1对mod的逆元为1 
    //计算从2到mod的数对mod的逆元 
    for(int i=2;i<=9972;++i){
        inv[i]=quickPow(i,MOD-2);
    }
    while(scanf("%d",&N)==1){ 
        pre[0]=1;
        scanf("%s",s+1);
        int n=strlen(s+1);
        //计算前缀积 
        for(int i=1;i<=n;++i){
            pre[i]=pre[i-1]*(s[i]-28)%MOD;
        }
        while(N--){
            int a,b;
            scanf("%d%d",&a,&b); 
            printf("%d\n",pre[b]*inv[pre[a-1]]%MOD);
        }
    }
    return 0;
}

思路

这道题就是求任意区间的前缀积，因为是任意区间，所以采取的计算结果的方案是这样的：

假如让求a到b的前缀积，我们就用从1到b的前缀积除以从1到a-1的前缀积，这样就得到了a到b的前缀积，问题是一个除法的模运算很麻烦，模运算是不能加到括号里的，但是如果变成乘法运算，那就可以把模运算加到括号里了，这时候就要用到逆元了，这里用的是用费马小定理来求的逆元，如果要求a对mod的逆元，那就等于\(a^{mod-2}\) ,这时候就涉及到求一个数的次方了，如果次方小还可以，但是次方太大的话，就会超时，这时，还会用到快速幂，这样就能完美求出逆元了。