这题的$O(n^2)$暴力可以拿到$95$分，用哈希预处理出$f_i$表示以$i$结尾的AA串数量，再用哈希和$f_i$统计答案即可

然后考虑正解，设$f_i$表示以$i$开头的AA串数量，$g_i$表示以$i$结尾的AA串数量，那么答案就是$\sum\limits_{i=1}^{n-1}g_if_{i+1}$，现在的问题就是预处理$f$和$g$

枚举AA串中A的长度$L$，把整个字符串中的$i,i+L,\cdots$称为“关键点”，那么一个AA串必定跨越两个关键点

对于每两个相邻的关键点$u,v(v=u+L)$，我们求出$x=\text{lcp}(S_{u\cdots n},S_{v\cdots n}),y=\text{lcs}(S_{1\cdots u},S_{1\cdots v})$（这里的lcs是最长公共 后缀），那么$S_{u-y+1\cdots u+x-1}=S_{v-y+1\cdots v+x-1}$，这时如果$x+y-1\geq L$，说明我们找到了一些合法的AA，它可以起始于$[u-y+1,u+x-L]$并终止于$[v+x-L,v+x-1]$，区间$+1$直接差分即可（注意同样长度的AA不能在同一个位置出现多次，特判一下即可）

为了偷懒，对字符串的处理我用了二分+哈希，总时间复杂度$O(n\log_2^2n)$，可是这毒瘤数据居然卡自然溢出哈希...不过大概也是我的姿势水平不太够

UPD：被kcz大爷hack了，不想改了...

UPD：改了...用SA求lcp和lcs

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;char s[30010];int n;struct pr{	int c[2],i;	pr(int a=0,int b=0,int d=0){c[0]=a;c[1]=b;i=d;}};bool operator!=(pr a,pr b){return a.c[0]!=b.c[0]||a.c[1]!=b.c[1];}struct sa{	char s[30010];	int rk[60010],sa[30010],h[30010],c[30010];	pr p[30010],q[30010];	void reset(){		memset(s,0,sizeof(s));		memset(rk,0,sizeof(rk));	}	void sort(int f){		int i,m=0;		for(i=1;i<=n;i++)m=max(m,p[i].c[f]);		memset(c,0,(m+1)<<2);		for(i=1;i<=n;i++)c[p[i].c[f]]++;		for(i=1;i<=m;i++)c[i]+=c[i-1];		for(i=n;i>0;i--)q[c[p[i].c[f]]--]=p[i];		memcpy(p,q,(n+1)*12);	}	int mn[30010][15],lg[30010];	void suf(){		int i,j,l,m;		for(i=1;i<=n;i++)rk[i]=s[i]-'a'+1;		for(l=1;l<=n;l<<=1){			for(i=1;i<=n;i++)p[i]=pr(rk[i],rk[i+l],i);			sort(1);			sort(0);			for(i=1,m=0;i<=n;i++){				if(p[i]!=p[i-1])m++;				rk[p[i].i]=m;			}		}		for(i=1;i<=n;i++)sa[rk[i]]=i;		for(i=1,l=0;i<=n;i++){			if(l)l--;			while(s[i+l]==s[sa[rk[i]-1]+l])l++;			h[rk[i]]=l;		}		for(i=1;i<=n;i++)mn[i][0]=h[i];		for(j=1;j<15;j++){			for(i=1;i+(1<
        
         <=n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);		}		for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;	}	int query(int l,int r){		int k=lg[r-l+1];		return min(mn[l][k],mn[r-(1<
         
          rk[y])swap(x,y);		return query(rk[x]+1,rk[y]);	}}fw,bw;int lcp(int x,int y){	return fw.lcp(x,y);}int lcs(int x,int y){	return bw.lcp(n-x+1,n-y+1);}int f[30010],g[30010];void add(int*a,int l,int r){	if(l>r)return;	a[l]++;	a[r+1]--;}void work(){	int L,i,a,b,ef,eg;	ll ans;	scanf("%s",s+1);	n=strlen(s+1);	fw.reset();	bw.reset();	for(i=1;i<=n;i++)fw.s[i]=bw.s[n-i+1]=s[i];	fw.suf();	bw.suf();	memset(f,0,sizeof(f));	memset(g,0,sizeof(g));	for(L=1;L<=n>>1;L++){		ef=eg=0;		for(i=1;i+L<=n;i+=L){			a=lcp(i,i+L);			b=lcs(i,i+L);			if(a+b-1>=L){				add(f,max(i-b+1,ef+1),i+a-L);				ef=max(ef,i+a-L);				add(g,max(i+L-b+L,eg+1),i+L+a-1);				eg=max(eg,i+L+a-1);			}		}	}	for(i=1;i<=n;i++){		f[i]+=f[i-1];		g[i]+=g[i-1];	}	ans=0;	for(i=1;i