费马小定理求逆元模板题

problem Description

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

(H(s)=prod_{i=1}^{ileq len(s)}(s_{i}-28)(mod 9973))

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

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

Input

多组测试数据，每组测试数据第一行是一个正整数N，代表询问的次数，第二行一个字符串，代表题目中的大字符串，接下来N行，每行包含两个正整数a和b，代表询问的起始位置以及终止位置。

(1leq Nleq 1,000)

(1leq len(string) leq 100,000)

(1leq a,bleq len(string))

Output

对于每一个询问，输出一个整数值，代表大字符串从 a 位到 b 位的子串的哈希值。

Sample Input

2
ACMlove2015
1 11
8 10
1
testMessage
1 1

Sample Output

6891
9240
88

题解

#include<iostream>
#include<cstring>
using namespace std;
#define MOD 9973 //要%的数 
int inv[10000];//存放逆元的数组 
int pre[100005];//存放前缀积 
char s[100005];//存放字符串
//快速幂，因为费马小定理要求一个数的(mod-2)次方
//a存放底数，b存放幂指数 
int quickPow(int a,int b){
	int r=1;//存放答案
	//不断迭代 
	while(b){
		//判断b是不是奇数 
		if(b&1){
			//b如果是奇数，将结果乘一个底数，同时结果模一下，防止数据过大 
			r=r*a%MOD;
		}
		b>>=1;//b右移一位，相当于除以2 
		a=a*a%MOD;//底数增大一倍 
	}
	return r;
}

int main(){
	int N,i,j,k;
	inv[1]=1;//1对mod的逆元为1 
	//计算从2到mod的数对mod的逆元 
	for(int i=2;i<=9972;++i){
		inv[i]=quickPow(i,MOD-2);
	}
	while(scanf("%d",&N)==1){ 
		pre[0]=1;
		scanf("%s",s+1);
		int n=strlen(s+1);
		//计算前缀积 
		for(int i=1;i<=n;++i){
			pre[i]=pre[i-1]*(s[i]-28)%MOD;
		}
		while(N--){
			int a,b;
			scanf("%d%d",&a,&b); 
			printf("%d
",pre[b]*inv[pre[a-1]]%MOD);
		}
	}
	return 0;
}

思路

这道题就是求任意区间的前缀积，因为是任意区间，所以采取的计算结果的方案是这样的：

假如让求a到b的前缀积，我们就用从1到b的前缀积除以从1到a-1的前缀积，这样就得到了a到b的前缀积，问题是一个除法的模运算很麻烦，模运算是不能加到括号里的，但是如果变成乘法运算，那就可以把模运算加到括号里了，这时候就要用到逆元了，这里用的是用费马小定理来求的逆元，如果要求a对mod的逆元，那就等于(a^{mod-2}) ,这时候就涉及到求一个数的次方了，如果次方小还可以，但是次方太大的话，就会超时，这时，还会用到快速幂，这样就能完美求出逆元了。