哈希如果自然溢出的话会匹配错误，所以哈希一定要模上一个数，此贴完结，算是告诫后人。
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define N 1919810
#define p 1000000007
#define int long long
using namespace std;
int fi[N],ps[N],tot,base=31,t,n;
int a[N],b[N];
string lz;
void csh_hash(){
fi[0]=1;
for(int i=1;i<1919810;i++)fi[i]=(fi[i-1]*base)%p;
}
struct string_hash{
int h[N];
void set(string s){
int n=s.size();
for(int i=0;i<n;i++)h[i]=(h[i-1]*base+(s[i]-'b'))%p;
}
int query(int l,int r){return ((h[r]-h[l-1]*fi[r-l+1]%p)+p)%p;}
}hs;
int lcs(int x,int y,int len){
int l=0,r=len;
while(l<=r){
int mid=(l+r)>>1;
if(hs.query(x-mid+1,x)==hs.query(y-mid+1,y))l=mid+1;
else r=mid-1;
}
return r;
}
int lcp(int x,int y,int len){
int l=0,r=n-y+1;
while(l<=r){
int mid=(l+r)>>1;
if(hs.query(x,x+mid-1)==hs.query(y,y+mid-1))l=mid+1;
else r=mid-1;
}
return r;
}
signed main(){
//freopen("P1117_13.in","r",stdin);
scanf("%lld",&t);
csh_hash();
while(t--){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>lz;
lz="0"+lz;
hs.set(lz);
n=lz.size()-1;
//printf("n:%d\n",n);
for(int len=1;len<=n/2;len++){
int j=len,k=len*2;
while(k<=n){
int l=max(k-lcs(j,k,len)+len,k),r=min(k+lcp(j,k,len)-1,k+len-1);
if(l<=r){
b[l]++;
b[r+1]--;
a[l-2*len+1]++;
a[r-2*len+2]--;
}
j+=len,k+=len;
}
}
for(int i=1;i<=n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
int ans=0;
for(int i=1;i<=n-1;i++)ans+=a[i+1]*b[i]%p;
printf("%lld\n",ans);
}
return 0;
}
/*
563349754956
161455324997
76621205738
70150901846
40842068960
6056659
2820346
3357795
2628223
22817
563349754956
161455324997
76621205738
70150901846
40842068960
6056659
2820346
3357795
2628223
10884
*/
```
by 黑影洞人 @ 2022-08-19 08:57:18
@[黑影洞人](/user/285617) /bx
by Link_Cut_Y @ 2023-07-12 07:47:50