发现一个奇怪的事情：因为我平时写哈希都是写单模数哈希，因此这次做这道题时也很顺手地写了单模哈希，结果交上去只有 95pts。

我十分疑惑，查了半天查不出错，翻了一下题解区和其他用户的几条 AC 记录，发现大家的哈希都没有取模，于是我把取模去掉试着交了一发，结果就过了。

有没有大佬能解释一下是怎么回事？蒟蒻感激不尽。

95pts代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int k=0;
	bool f=false;
	char c=getchar();
	while(!isdigit(c)){
		f=f||c=='-';
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<3)+(k<<1)+c-'0';
		c=getchar();
	}
	return f?-k:k;
}
inline void write(int d,char end_ch='\n'){
	if(d<0){
		putchar('-');
		d=-d;
	}
	int stk[32],top=0;
	do{
		top++;
		stk[top]=d%10;
		d/=10;
	}while(d);
	for(int i=top;i;i--){
		putchar(stk[i]+'0');
	}
	putchar(end_ch);
}
const int N=3e5+5,base=131,mod=1145141999;
string s;
int n,hsh[N],base_pow[N],ans[N];
inline int get_hash(int x,int y){
	return (hsh[y]+mod-hsh[x-1]*base_pow[y-x+1]%mod)%mod;//注意此处的取模！
}
int get_len(int x,int y){
	int l=0,r=min(n-x+1,n-y+1);
	while(l<r){
		int mid=(l+r+1)>>1;
		if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
bool cmp(int d1,int d2){
	int o=get_len(d1,d2);
	return s[d1+o]<s[d2+o];
}
signed main(){
	cin>>s;
	n=s.length();
	s=" "+s+(char)10;
	base_pow[0]=1;
	for(int i=1;i<=n;i++){
		ans[i]=i;
		hsh[i]=(hsh[i-1]*base%mod+s[i]-'0')%mod;//注意此处的取模！
		base_pow[i]=base_pow[i-1]*base%mod;
	}
	stable_sort(ans+1,ans+n+1,cmp);
	for(int i=1;i<=n;i++){
		write(ans[i]-1,i==n?'\n':' ');
	}
	for(int i=1;i<=n;i++){
		write((i==1)?0:get_len(ans[i],ans[i-1]),' ');
	}
	return 0;
}

100pts代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int k=0;
	bool f=false;
	char c=getchar();
	while(!isdigit(c)){
		f=f||c=='-';
		c=getchar();
	}
	while(isdigit(c)){
		k=(k<<3)+(k<<1)+c-'0';
		c=getchar();
	}
	return f?-k:k;
}
inline void write(int d,char end_ch='\n'){
	if(d<0){
		putchar('-');
		d=-d;
	}
	int stk[32],top=0;
	do{
		top++;
		stk[top]=d%10;
		d/=10;
	}while(d);
	for(int i=top;i;i--){
		putchar(stk[i]+'0');
	}
	putchar(end_ch);
}
const int N=3e5+5,base=131,mod=1145141999;
string s;
int n,hsh[N],base_pow[N],ans[N];
inline int get_hash(int x,int y){
	return hsh[y]-hsh[x-1]*base_pow[y-x+1];//注意此处删去了取模！
}
int get_len(int x,int y){
	int l=0,r=min(n-x+1,n-y+1);
	while(l<r){
		int mid=(l+r+1)>>1;
		if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
bool cmp(int d1,int d2){
	int o=get_len(d1,d2);
	return s[d1+o]<s[d2+o];
}
signed main(){
	cin>>s;
	n=s.length();
	s=" "+s+" ";
	base_pow[0]=1;
	for(int i=1;i<=n;i++){
		ans[i]=i;
		hsh[i]=hsh[i-1]*base+s[i]-'0';//注意此处删去了取模！
		base_pow[i]=base_pow[i-1]*base;
	}
	stable_sort(ans+1,ans+n+1,cmp);
	for(int i=1;i<=n;i++){
		write(ans[i]-1,i==n?'\n':' ');
	}
	for(int i=1;i<=n;i++){
		write((i==1)?0:get_len(ans[i],ans[i-1]),' ');
	}
	return 0;
}