首页 > 代码库 > [HDU5685]2016"百度之星" - 资格赛 Problem A

[HDU5685]2016"百度之星" - 资格赛 Problem A

2024-11-27 06:05:39   204人阅读

题目大意：给你一个字符串，和一些问题，每个问题问你[l,r]子串的哈希值是多少。

哈希值计算方法为：$H(s)=\prod _{i=1} ^{i\leq len(s)}(s_i-28)(mod\ 9973)$。

其中$s_i$代表 S[i] 字符的 ASCII 码。

解题思路：我们知道，要算区间[l,r]所有的和，就可以用$O(n)$的时间预处理出数组t，令$t[i]$表示前i个数的和，那么$t[r]-t[l-1]$即为区间[l,r]所有之和，询问时间复杂度$O(1)$，这就是维护前缀和的做法。

那么这道题，我们也可以维护一个前缀，令$t[i]$表示前i个字符的哈希值，然后[l,r]子串的哈希值就为$\frac{t[r]}{t[l-1]}$。

等等，有个取模运算，那这样做不就WA了？没事，我们把$t[r]$除以$t[l-1]$改成$t[r]$乘($t[l-1]$的乘法逆元)即可。计算乘法逆元用扩展欧几里得算法即可。

时间复杂度$O(Tn\log (a+b))$，其中T为数据组数。

注意事项：$t[0]$一定要赋成1，否则你怎么算答案都是0！！！

C++ Code：

#include<cstdio>#include<cstring>using namespace std;#define p 9973int n;char s[100004];int t[100004];int exGcd(int a,int b,int& x,int& y){	if(b==0){		x=1,y=0;		return a;	}	int gcd=exGcd(b,a%b,x,y);	int q=x;	x=y;	y=q-a/b*y;	return gcd;}int calc(int l,int r){	int x,y;	exGcd(t[l-1],p,x,y);	return t[r]*((x%p+p)%p)%p;}int main(){	while(scanf("%d",&n)!=EOF){		scanf("%s",s+1);		t[0]=1;		int len=strlen(s+1);		for(int i=1;i<=len;++i)t[i]=t[i-1]*(s[i]-28)%p;		int l,r;		while(n--){			scanf("%d%d",&l,&r);			printf("%d\n",calc(l,r));		}	}	return 0;}

 

[HDU5685]2016"百度之星" - 资格赛 Problem A


联系
我们