Luogu
LOJ
UOJ
BZOJ
设\(f_i,g_i\)分别表示以\(i\)结尾/开头的形如\(AA\)的串的个数，那么答案就是\(\sum f_ig_{i+1}\)。
考虑枚举\(A\)的长度\(len\)，那么形如\(AA\)的串一定会过至少两个下标为\(len\)的倍数的位置（我们称之为关键位置）。
对于任意相邻两个关键位置\(i,j=i+len\)，它们对答案有\(1\)的贡献当且仅当\(lcp(suf(i),suf(j))+lcs(pre(i-1),pre(j-1))\ge len\)。
记\(x=lcp(suf(i),suf(j)),y=lcs(pre(i-1),pre(j-1)\)，那么这个\(AA\)串的结尾可以落在\([i-y,i+x-len+1)\)。
先维护\(f,g\)的差分再前缀和还原即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
int min(int a,int b){return a<=b? a:b;}
void swap(int &x,int &y){x^=y^=x^=y;}
const int N=3e4+7;
int t[N],x[N],y[N],Log[N],st[N],ed[N],n;
void init(){memset(x,0,sizeof x),memset(y,0,sizeof y);}
void Init(){memset(st,0,sizeof st),memset(ed,0,sizeof ed);}
struct SuffixArray
{
int sa[N],rnk[N],h[N][20],m;
char s[N];
void rsort()
{
for(int i=0;i<=m;++i) t[i]=0;
for(int i=1;i<=n;++i) ++t[x[y[i]]];
for(int i=1;i<=m;++i) t[i]+=t[i-1];
for(int i=n;i;--t[x[y[i]]],--i) sa[t[x[y[i]]]]=y[i];
}
void ssort()
{
int i,l,p;
for(i=1;i<=n;++i) x[i]=s[i]-‘a‘+1,y[i]=i;
m=26,rsort();
for(l=1,p=0;p<n;m=p,l<<=1)
{
for(p=0,i=n-l+1;i<=n;++i) y[++p]=i;
for(i=1;i<=n;++i) if(sa[i]>l) y[++p]=sa[i]-l;
rsort(),swap(x,y),x[sa[1]]=p=1;
for(i=2;i<=n;++i) x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+l]==y[sa[i]+l])? p:++p;
}
}
void geth()
{
int lcp=0,i,j;
for(i=1;i<=n;++i) rnk[sa[i]]=i;
for(i=1;i<=n;++i)
{
if(lcp) --lcp;
if(rnk[i]==n) continue;
j=sa[rnk[i]+1];
while(s[i+lcp]==s[j+lcp]) ++lcp;
h[rnk[i]][0]=lcp;
}
for(i=1;i<=15;++i) for(j=1;j<=n&&j+(1<<i-1)<=n;++j) h[j][i]=min(h[j][i-1],h[j+(1<<i-1)][i-1]);
}
int LCP(int x,int y)
{
x=rnk[x],y=rnk[y];
if(x>y) swap(x,y);
int k=Log[y-x];
return min(h[x][k],h[y-(1<<k)][k]);
}
}A,B;
int main()
{
int i,T=read(),j,x,y,t,len;
LL ans;
for(i=2;i<N;++i) Log[i]=Log[i>>1]+1;
while(T--)
{
Init(),init(),scanf("%s",A.s+1),n=strlen(A.s+1),A.ssort(),A.geth();
for(i=1;i<=n;++i) B.s[i]=A.s[n-i+1]; init(),B.ssort(),B.geth();
for(len=1;len<=n>>1;++len)
for(i=len,j=len<<1;j<=n;i+=len,j+=len)
{
x=min(A.LCP(i,j),len),y=min(B.LCP(n-i+2,n-j+2),len-1);
if(x+y>=len) t=x+y-len+1,++st[i-y],--st[i-y+t],++ed[j+x-t],--ed[j+x];
}
for(i=1;i<=n;++i) st[i]+=st[i-1],ed[i]+=ed[i-1];
for(ans=0,i=1;i<=n;++i) ans+=1ll*ed[i]*st[i+1];
printf("%lld\n",ans);
}
}
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7+7;
struct node{int n,m,k;};
int operator<(node a,node b){return a.n==b.n? (a.m==b.m? a.k<b.k:a.m<b.m):a.n<b.n;};
int read(){int x;cin>>x;return x;}
int lim,num[2000],flag[N],prime[N],mu[N],mus[N];
map<int,int>mp;
map<node,LL>Ans;
int smu(int x)
{
if(x<=lim) return mus[x];
if(mp[x]) return mp[x];
int sum=1,i=2,j=sqrt(x);
for(;i<=j;++i) sum-=smu(x/i);
for(;i<=x;i=j+1) j=x/(x/i),sum-=(j-i+1)*smu(x/i);
return mp[x]=sum;
}
LL solve(int n,int m,int k)
{
if(!n||!m) return 0;
node tmp=node{n,m,k};
LL sum=0;
if(Ans[tmp])return Ans[tmp];
if(k==1)
{
if(n>m) swap(n,m);
int i,j,now,last;
for(i=1,last=0;i<=n;i=j+1,last=now) j=min(n/(n/i),m/(m/i)),now=smu(j),sum+=1ll*(n/i)*(m/i)*(now-last);
Ans[node{m,n,k}]=sum;
}
else for(int i=1;i<=num[0]&&num[i]<=k;++i) if(k%num[i]==0&&mu[num[i]]) sum+=solve(m/num[i],n,num[i])*mu[num[i]];
return Ans[tmp]=sum;
}
int main()
{
int n=read(),m=read(),k=read(),i,j;lim=min(10000000,max(k,min(n,m))),mu[1]=1;
for(i=2;i<=lim;++i)
{
if(!flag[i]) prime[++prime[0]]=i,mu[i]=-1;
for(j=1;j<=prime[0]&&i*prime[j]<=lim;++j)
{
flag[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i]; else{mu[i*prime[j]]=0;break;}
}
}
for(i=1;i<=lim;++i) mus[i]=mus[i-1]+mu[i];
for(i=1;i<=k;++i) if(!(k%i)) num[++num[0]]=i;
return !printf("%lld",solve(n,m,k));
}
原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/13019222.html