Problem A

Accepts: 599

Submissions: 5110

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

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

$S_{i}$ 代表 S[i] 字符的 ASCII 码。

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

6891
9240
88
想A这道题 一定要懂得逆元  
比如i*j%9973=1  那么j就是i的逆元
有两种方法求逆元：

     
      对字符串s，从左到右，对每个字串存储其哈希值dp。如果只考虑乘法的消耗，这一步的时间复杂度是O(len(s))。
      对于任一子串，子串 S(a...b)的 hash 值： H(s)=dp[b]/dp[a?1]%mod
      1/dp[a?1]%9973就是dp[a-1]的逆元。求逆元的时间复杂度是O(log(9973））
     
1,、就是对所有逆元打表  怎么求逆元呢？  看下图  如果你想问怎么来的 请百度。。。
取模下的乘法  就是乘上它的逆元


     
2、dp[b] / dp[a-1] % mod = (dp[b] * （dp[a-1] ^ (mod-2) % mod）)% mod;用快速幂求；代码如下：
#include<stdio.h>  
#include<string.h>  
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
#define LL long long  
const LL maxm=1e5+10;  
const LL mod=9973;  
string s;  
LL dp[maxm];  
LL quickmod(LL a,LL b)  
{  LL sum=1;  while(b)  {  if(b&1)  sum=(sum*a)%mod;  b>>=1;  a=(a*a)%mod;  }  return sum;  
}  
int main()  
{  LL n;  while(scanf("%I64d",&n)!=EOF)  {  cin>>s;  dp[0]=1;  for(LL i=1; i<=s.length(); i++)  {  dp[i]=(dp[i-1]*(s[i-1]-28))%mod;  }  LL l,r;  for(LL i=0; i<n; i++)  {  scanf("%I64d%I64d",&l,&r);  if(l>r)  {  swap(l,r);  }  printf("%I64d\n",(dp[r]*(quickmod(dp[l-1],mod-2)%mod))%mod);  }  }  return 0;  


代码2；
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL __int64
#define mod 9973
using namespace std;
LL inv[100010]={0};
char s[100100];
LL H[100100];
//  计算逆元方法一：
LL mod_pow(LL x, LL n) {LL res = 1;while(n) {if(n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res%mod;
}
int main()
{inv[1]=1;inv[0]=1;//  计算逆元方法二:for(int i=2;i<mod+1;i++)
   {inv[i]=(mod-mod/i)*inv[mod%i]%mod;}int n,l,r;H[0]=1;while(~scanf("%d",&n)){scanf("%s",s);int len=strlen(s);for(int i=1;i<=len;i++)       // 定义变量获取长度降低时间;H[i]=H[i-1]*(s[i-1]-28)%mod;while(n--){scanf("%d%d",&l,&r);if(r<l) swap(l,r);//printf("%I64d\n",H[r]*mod_pow(H[l-1],mod-2)%mod);printf("%d\n",H[r]*inv[H[l-1]]%mod);}}return 0;
}

【逆元】

Problem A