题目
题解
跟这道题差不多一个处理方法，枚举$x=j-i$，每隔$x$距离放一个标志，求相邻标志的$LCP$和$LCS$（最长公共后缀），建两个后缀数组就可以处理
每次更新答案就是对于一段区间加三部分答案，二维差分即可$O(1)$维护
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=5e5+5,mod=1e9+7,inv2=5e8+4;
int n,m;
int Log[MAX];
struct SA{
int het[MAX],h[MAX],tax[MAX],sa[MAX],rk[MAX];
int f[20][MAX];
char a[MAX];
void rsort()
{
for(int i=0;i<=m;tax[i++]=0);
for(int i=1;i<=n;++tax[rk[h[i]]],++i);
for(int i=1;i<=m;tax[i]+=tax[i-1],++i);
for(int i=n;i>=1;sa[tax[rk[h[i]]]--]=h[i],--i);
}
bool cmp(int *a,int x,int y,int w) {return a[x]==a[y]&&a[x+w]==a[y+w];}
void Suffix()
{
for(int i=1;i<=n;++i)
rk[i]=a[i],h[i]=i;
m=127,rsort();
for(int p=1,w=1,i;p<n;w+=w,m=p)
{
for(p=0,i=n-w+1;i<=n;++i)
h[++p]=i;
for(i=1;i<=n;++i)
if(sa[i]>w) h[++p]=sa[i]-w;
rsort(),swap(rk,h),rk[sa[1]]=p=1;
for(i=2;i<=n;++i)
rk[sa[i]]=cmp(h,sa[i],sa[i-1],w)?p:++p;
}
int j,k=0;
for(int i=1;i<=n;het[rk[i++]]=k)
for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
}
void Init()
{
for(int i=1;i<=n;++i)
f[0][i]=het[i];
for(int i=1;i<=19;++i)
for(int j=1;j<=n-(1<<i-1);++j)
f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);
}
int LCP(int l,int r)
{
if(l==r) return l;
l=rk[l],r=rk[r];
if(l>r) swap(l,r);
int t=Log[r-l];
return min(f[t][l+1],f[t][r-(1<<t)+1]);
}
}a,b;
struct p{
int a,b,c;
p(int A=0,int B=0,int C=0) {a=A,b=B,c=C;}
}ans[MAX];
p operator+ (p a,p b) {return p((a.a+b.a)%mod,(a.b+b.b)%mod,(a.c+b.c)%mod);}
void Upt(int L,int R,int a,int b,int c) {ans[L]=ans[L]+p(a,b,c),ans[R]=ans[R]+p(-a,-b,-c);}
int main()
{
scanf("%s",a.a+1),n=strlen(a.a+1),Log[0]=-1;
for(int i=1;i<=n;++i)
Log[i]=Log[i>>1]+1;
memcpy(b.a,a.a,sizeof(a.a)),reverse(b.a+1,b.a+1+n);
a.Suffix(),b.Suffix(),a.Init(),b.Init();
for(int i=1;i+i<=n;++i)
for(int l=i,r,rl,ll,L,R,v1,v2;l+i<=n;l+=i)
{
r=l+i,rl=min(i,a.LCP(l,r)),ll=b.LCP(n-l+1,n-r+1);
if(ll+rl-1>i) L=max(r,r+i-ll),R=r+rl,v1=i+ll+rl+1-R,v2=ll+rl-i-R,Upt(L,R,1,v1+v2,1ll*v1*v2%mod);
}
for(int i=1,Ans=0;i<=n;++i)
ans[i]=ans[i]+ans[i-1],(Ans+=(((1ll*ans[i].a*i%mod*i%mod+1ll*ans[i].b*i%mod)%mod+ans[i].c)%mod+mod)%mod)%=mod,printf("%d\n",1ll*Ans*inv2%mod);
return 0;
}
