Problem A

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1302    Accepted Submission(s): 590 Problem Description 度熊手上有一本字典存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串。现在麻烦来了，他忘记了原来的字符串都是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到： H(s)=∏i≤len(s)i=1(Si−28) (mod 9973) Si 代表 S[i] 字符的 ASCII 码。 请帮助度熊计算大字符串中任意一段的哈希值是多少。   Input 多组测试数据，每组测试数据第一行是一个正整数 N ，代表询问的次数，第二行一个字符串，代表题目中的大字符串，接下来 N 行，每行包含两个正整数 a 和 b ，代表询问的起始位置以及终止位置。 1≤N≤1,000 1≤len(string)≤100,000 1≤a,b≤len(string)   Output 对于每一个询问，输出一个整数值，代表大字符串从 a 位到 b 位的子串的哈希值。   Sample Input 2 ACMlove2015 1 11 8 10 1 testMessage 1 1   Sample Output 6891 9240 88  

思路

一道求逆元的题目，先用Ｏ（ｎ）的时间求出每个位置处的ｈａｓｈ值

对于每个输入ａ和ｂ

ａｎｓ　＝　ｈａｓｈ（ｂ）/ｈａｓｈ（a-1）;

这里需要使用求逆元的知识，用扩展欧几里德，或是费马小定理

///AC代码 /* *********************************************** ┆ ┏┓　　　┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　━　　　┃ ┆ ┆┃　┳┛　┗┳　┃ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　┻　　　┃ ┆ ┆┗━┓　马　┏━┛ ┆ ┆　　┃　勒　┃　　┆　　　　　　 ┆　　┃　戈　┗━━━┓ ┆ ┆　　┃　壁　　　　　┣┓┆ ┆　　┃　的草泥马　　┏┛┆ ┆　　┗┓┓┏━┳┓┏┛ ┆ ┆　　　┃┫┫　┃┫┫ ┆ ┆　　　┗┻┛　┗┻┛ ┆ ************************************************ */ #include <iostream> #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <algorithm> #include <functional> #define PI acos(-1) #define eps 1e-8 #define inf 0x3f3f3f3f #define debug(x) cout<<"---"<<x<<"---"<<endl const int MOD = 9973; typedef long long ll; using namespace std; ///费马小定理求逆元 ll PowMod(ll a, ll b, ll MOD) { ll ret = 1; while (b) { if (b & 1) { ret = (ret * a) % MOD; } a = (a * a) % MOD; b >>= 1; } return ret; }//快速幂 char s[100500]; int hashh[100500]; int main() { ///std::ios::sync_with_stdio(false);cin.tie(0); int n; hashh[0] = 1; while (scanf("%d", &n) != EOF) { scanf("%s", s + 1); int len = strlen(s + 1); for (int i = 1; i < len + 1; i++) { hashh[i] = hashh[i - 1] * (s[i] - 28) % MOD; } int start, endd; while (n--) { scanf("%d%d", &start, &endd); ll ans = hashh[endd] * PowMod(hashh[start - 1], MOD - 2, MOD) % MOD; printf("%I64d\n", ans); } } return 0; } /************************************************ ┆ ┏┓　　　┏┓ ┆ ┆┏┛┻━━━┛┻┓ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　━　　　┃ ┆ ┆┃　┳┛　┗┳　┃ ┆ ┆┃　　　　　　　┃ ┆ ┆┃　　　┻　　　┃ ┆ ┆┗━┓　 　┏━┛ ┆ ┆　　┃　 　┃　　┆　　　　　　 ┆　　┃　 　┗━━━┓ ┆ ┆　　┃　 AC代马 　　┣┓┆ ┆　　┃　 　　┏┛┆ ┆　　┗┓┓┏━┳┓┏┛ ┆ ┆　　　┃┫┫　┃┫┫ ┆ ┆　　　┗┻┛　┗┻┛ ┆ ************************************************ */