2016「百度の星」-資格試合(Astar Round 1)ProblemA(乗算逆元)

Problem A  
 
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
Problem Description
度熊の手には辞書に大量の単語が格納されていたが、ある時、彼はすべての単語を長い文字列に構成した.今面倒になって、彼は元の文字列が何なのか忘れて、不思議なことに彼は意外にも元の文字列のハッシュ値を覚えています.文字列のハッシュ値は、次の式で計算されます.
H(s)=\prod_{i=1}^{i\leq len(s)}(S_{i}-28)\(mod\9973)H(s)=∏​i=1​i≤len(s)​​(S​i​​−28) (mod 9973)
S_{i}S iはS[i]文字のASCIIコードを表す.
大きな文字列のいずれかのセグメントのハッシュ値を計算するのに役立ちます.
Input
複数組のテストデータ、各組のテストデータの第1行は1つの正の整数NNで、問い合わせの回数を代表して、第2行の1つの文字列、テーマの中の大きい文字列を代表して、次のNN行、各行は2つの正の整数aaとbbを含んで、問い合わせの開始位置と終了位置を代表します.
1\leq N\leq 1,0001≤N≤1,000
1\leq len(string)\leq 100,0001≤len(string)≤100,000
1\leq a,b\leq len(string)1≤a,b≤len(string)
Output
各クエリについて、aaビットからbbビットまでの大きな文字列のサブ列のハッシュ値を表す整数値が出力される.
Sample Input

2
ACMlove2015
1 11
8 10
1
testMessage
1 1

Sample Output

6891
9240
88

問題を解く考え方:文字列とn回の質問をします.
毎回
文字列区間[a,b]のハッシュ値を求めます
H(s)=∏​i=1​i≤len(s)​​(S​i​​−28) (mod 9973)
実は区間[a,b]のハッシュ値が要求され、[0,b]のハッシュ値/[0,a-1]のハッシュ値に変換することができる.
まず[0,b]のハッシュ値と[0,a]のハッシュ値は求めやすく、ans[i+1]=ans[i]*(s[i]-28)%modを利用すればよい
しかし、積値は型取りされるため、除算において型取り演算は同余を満たさない
このときは逆算元を思い浮かべますが、幸いにも逆算元のテンプレートが用意されていて、あとはテンプレートを貼るだけです
タイトルリンク→HDU 5685 ProblemA

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 100005;
const int M = 40;
const int inf = 100000000;
const int mod = 9973;
char s[N];
int ans[N];
__int64 Quick_Mod(int a,int b)//     
{  
    __int64 res = 1,term = a % mod;  
    while(b)  
    {  
        if(b & 1) res = (res * term) % mod;  
        term = (term * term) % mod;  
        b >>= 1;  
    }  
    return res;  
}  
int main()
{
    int n,i,j,a,b;
    while(~scanf("%d",&n))
    {
        scanf("%s",s);
        ans[0]=1;
        ans[1]=(s[0]-28)%mod;
        for(i=1;s[i]!='\0';i++)
            ans[i+1]=ans[i]*(s[i]-28)%mod;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
              printf("%d
",(ans[b]*Quick_Mod(ans[a-1],mod-2))%mod);//  (ans[b]/ans[a-1])%mod  
        }
    }
    return 0;
}

菜鳥成長記