其实题目不算很难，但是我调试的时候被玄学了，for循环里不写空格会RE，写了才能过。神**调了一个多小时是这么个不知道是什么的玩意(真事，可以问i207M=。=)，心态爆炸
发现我们只要找AA或者BB就行了，因为另一半反过来再做一次然后拼起来就可以了，那么就设$stp[i]$表示从$i$开始有多少个$AA$这样的串，$edp[i]$表示在$i$结束有多少个$AA$这样的串。一个个位置暴力求是$O(n^2)$的，可以得95pts(雾。
AC做法是一种巧妙(套路?毕竟我做题少)的做法。枚举一个len把串分成长度为$len$的段，然后发现形如$AA$的字符串一定至少跨过了两个分界点，那么我们求一下这两个分界点的$LCP$和$LCS$，看看是不是超过$len$即可，然后具体的贡献可以用差分实现，时间复杂度$O(n\log n)$(不知道为啥$n$只出了30000，可能是为了放哈希+二分的$O(n\log^2 n)$过去？)。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
struct a
{
char str[N];
int sec[N],bkt[N];
int sar[N],rnk[N],hgt[N],st[N][K];
int len,siz;
void Set()
{
len=,siz=;
memset(sec,,sizeof sec);
memset(rnk,,sizeof rnk);
}
void Prework()
{
register int i;
for(i=;i<=len;i++)
rnk[i]=str[i]-'a'+,sec[i]=i;
}
void Basenum_Sort()
{
register int i;
for(i=;i<=siz;++i) bkt[i]=;
for(i=;i<=len;++i) ++bkt[rnk[i]];
for(i=;i<=siz;++i) bkt[i]+=bkt[i-];
for(i=len;i>=;--i) sar[bkt[rnk[sec[i]]]--]=sec[i];
}
void Suffix_Sort()
{
register int i;
int cnt=,pw=;
Basenum_Sort();
while(cnt<len)
{
cnt=;
for(i=;i<=pw;i++) sec[++cnt]=len-pw+i;
for(i=;i<=len;i++) if(sar[i]>pw) sec[++cnt]=sar[i]-pw;
Basenum_Sort(); swap(rnk,sec); rnk[sar[]]=cnt=;
for(i=;i<=len;i++)
cnt+=(sec[sar[i-]]!=sec[sar[i]]||sec[sar[i-]+pw]!=sec[sar[i]+pw]),rnk[sar[i]]=cnt;
pw<<=,siz=cnt;
}
}
void Getting_Height()
{
register int i,p=;
for(i=;i<=len;i++)
if(rnk[i]!=)
{
int r=sar[rnk[i]-];
while(str[r+p]==str[i+p]) p++;
hgt[rnk[i]]=p; if(p>) p--;
}
hgt[]=;
}
void Building_Table()
{
register int i,j;
for(i=;i<=len;i++)
st[i][]=hgt[i];
int lgg=log2(len);
for(i=;i<=lgg;i++)
for(j=;j<=len-(<<i)+;j++)
st[j][i]=min(st[j][i-],st[j+(<<(i-))][i-]);
}
int LCP_Query(int x,int y)
{
int xx=rnk[x],yy=rnk[y],lgg;
if(xx>yy) swap(xx,yy); xx++,lgg=log2(yy-xx+);
return min(st[xx][lgg],st[yy-(<<lgg)+][lgg]);
}
}SA[];
int n,lth,stp[N],edp[N];
void Init()
{
SA[].Set(),SA[].Set();
memset(stp,,sizeof stp);
memset(edp,,sizeof edp);
}
int main()
{
register int i,j,k,h;
scanf("%d",&n);
for(i=;i<=n;i++)
{
Init(); scanf("%s",SA[].str+);
SA[].len=SA[].len=lth=strlen(SA[].str+);
for(j=;j<=lth;j++)
SA[].str[j]=SA[].str[lth-j+];
for(j=;j<=;j++)
{
SA[j].Prework();
SA[j].Suffix_Sort();
SA[j].Getting_Height();
SA[j].Building_Table();
}
for(j=;j<=lth/;j++)
{
for(k=j,h=*j;h<=lth;k+=j,h+=j)
{
int l1=min(SA[].LCP_Query(k,h),j);
int l2=min(SA[].LCP_Query(lth-k+,lth-h+),j);
if(l1+l2>j)
{
stp[k-l2+]++,edp[h-l2+j]++;
stp[k+l1-j+]--,edp[h+l1]--;
}
}
}
long long ans=;
for(j=;j<=lth;j++)
stp[j]+=stp[j-],edp[j]+=edp[j-];
for(j=;j<lth;j++)
ans+=1ll*stp[j+]*edp[j];
printf("%lld\n",ans);
}
return ;
}
Upd on 2019.3.16：用SAM搞过去了，然而因为常数原因被同样复杂度的SA踩了
你问怎么做到同样复杂度？写个RMQ LCA就行了(我就因为写这个才学的RMQ LCA=。=)
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
struct SAM
{
char str[N];
int p[N],noww[N],goal[N];
int dfn[N],idf[N],fir[*N],st[N][K];
int trs[N][],fth[N],len[N],ndp[N];
int lth,lst,tot,cnt,dfo,app;
void Init()
{
cnt=dfo=app=,tot=lst=;
memset(p,,sizeof p);
memset(fth,,sizeof fth);
memset(len,,sizeof len);
memset(trs,,sizeof trs);
}
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
int Insert(int ch)
{
int nde=lst,newn=++tot;
lst=newn,len[newn]=len[nde]+;
while(nde&&!trs[nde][ch])
trs[nde][ch]=newn,nde=fth[nde];
if(!nde) fth[newn]=;
else
{
int tran=trs[nde][ch];
if(len[tran]==len[nde]+)
fth[newn]=tran;
else
{
int rnde=++tot; len[rnde]=len[nde]+;
for(int i=;i<=;i++) trs[rnde][i]=trs[tran][i];
fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
while(nde&&trs[nde][ch]==tran)
trs[nde][ch]=rnde,nde=fth[nde];
}
}
return newn;
}
void DFS(int nde)
{
idf[dfn[nde]=++dfo]=nde;
st[fir[nde]=++app][]=dfo;
for(int i=p[nde];i;i=noww[i])
DFS(goal[i]),st[++app][]=dfn[nde];
}
int LCA(int x,int y)
{
x=fir[x],y=fir[y];
if(x>y) swap(x,y);
int l2=log2(y-x+);
return idf[min(st[x][l2],st[y-(<<l2)+][l2])];
}
void Create()
{
for(int i=;i<=lth;i++)
ndp[i]=Insert(str[i]-'a');
for(int i=;i<=tot;i++)
Link(fth[i],i); DFS();
for(int i=;i<=;i++)
for(int j=;j+(<<i)-<=app;j++)
st[j][i]=min(st[j][i-],st[j+(<<(i-))][i-]);
}
int LCS(int x,int y)
{
int lca=LCA(ndp[x],ndp[y]);
return len[lca];
}
}s[];
int n,m,stp[N],edp[N];
void Init()
{
memset(stp,,sizeof stp);
memset(edp,,sizeof edp);
}
int main()
{
register int i,j,k,h;
scanf("%d",&n);
for(i=;i<=n;i++)
{
Init(); scanf("%s",s[].str+);
s[].lth=s[].lth=m=strlen(s[].str+);
for(j=;j<=m;j++) s[].str[j]=s[].str[m-j+];
s[].Init(),s[].Create();
s[].Init(),s[].Create();
for(j=;j<=(m>>);j++)
{
for(k=j,h=*j;h<=m;k+=j,h+=j)
{
int l1=min(s[].LCS(k,h),j);
int l2=min(s[].LCS(m-k+,m-h+),j);
if(l1+l2>j)
{
stp[k-l1+]++,edp[h-l1+j]++;
stp[k+l2-j+]--,edp[h+l2]--;
}
}
}
long long ans=;
for(j=;j<=m;j++) stp[j]+=stp[j-],edp[j]+=edp[j-];
for(j=;j<m;j++) ans+=1ll*stp[j+]*edp[j];
printf("%lld\n",ans);
}
return ;
}