HDU 5685 Problem A
度熊手上有一本字典存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串。现在麻烦来了，他忘记了原来的字符串都是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到： H(s)=∏i≤len(s)i=1(Si−28) (mod 9973) H(s)=∏i=1i≤len(s)(Si−28) (mod 9973) Si Si代表 S i i 字符的 ASCII 码。 请帮助度熊计算大字符串中任意一段的哈希值是多少。 Input 多组测试数据，每组测试数据第一行是一个正整数 N N，代表询问的次数，第二行一个字符串，代表题目中的大字符串，接下来 N N行，每行包含两个正整数 a a和 b b，代表询问的起始位置以及终止位置。 1≤N≤1,000 1≤N≤1,000 1≤len(string)≤100,000 1≤len(string)≤100,000 1≤a,b≤len(string) 1≤a,b≤len(string) Output 对于每一个询问，输出一个整数值，代表大字符串从 a a 位到 b b 位的子串的哈希值。 Sample Input 2 ACMlove2015 1 11 8 10 1 testMessage 1 1 Sample Output 6891 9240 88【分析】区间求积问题
预处理前缀积，因为模是质数，用乘法逆元代替除法运算
#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; const int maxn = 1e5 + 10; const int mod = 9973; char s[maxn]; typedef long long LL; LL quickpowmod(LL x,LL y,LL mod) { LL ans = 1; while(y){ if(y&1) ans = ans*x%mod; y >>= 1; x = x*x%mod; } return ans; } int main() { int n; while(~scanf("%d",&n)){ scanf("%s",&s); LL a[maxn]; a[0] = 1; int len = strlen(s); for(int i=1;i<=len;i++){ a[i] = a[i-1] * (s[i-1] - 28); a[i] %= mod; } while(n--){ int x,y; scanf("%d%d",&x,&y); printf("%lld\n",(a[y]*(quickpowmod(a[x-1],mod-2,mod)%mod))%mod); } } return 0; }