[HDU5685]Problem A

来源：

2016"百度之星" - 资格赛（Astar Round1）

思路：

首先处理出所有前缀的哈希$f$，对于所有的询问$[a,b]$，答案即为$frac{f[b]}{f[a-1]}$。
哈希值除法可以通过乘逆元实现。
注意循环时不能直接用$strlen(s)$作为判断条件，
因为$strlen()$函数是$O(n)$的复杂度，这样每次循环都会运行一次，就会把$O(n)$的循环退化成$O(n^2)$的。

#include<cstdio>
const int LEN=100001,mod=9973;
char s[LEN];
int f[LEN]={1};
int exgcd(const int a,const int b,int &x,int &y) {
    if(!b) {
        x=1;
        y=0;
        return a;
    }
    int t=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return t;
}
int main() {
    int n;
    while(~scanf("%d",&n)) {
        scanf("%s",s);
        for(unsigned i=0;s[i];i++) {
            f[i+1]=f[i]*(s[i]-28)%mod;
        }
        while(n--) {
            int a,b;
            scanf("%d%d",&a,&b);
            int x,y;
            exgcd(f[a-1],mod,x,y);
            printf("%d
",f[b]*(x+mod)%mod);
        }
    }
    return 0;
}