题意翻译

给定一个长度为n的小写字母串。问你有多少对相交的回文子 串（包含也算相交） 。 输入格式

第一行是字符串长度n(1<=n<=2*10^6)，第二行字符串 输出格式

相交的回文子串个数%51123987

题解

直接判断相交的回文串很难

那我们考虑找出所有不相交的回文串

数量就是所有以$i$结尾的回文串数乘以$i$后面的回文串数

以$i$结尾的回文串数就是在fail树里$i$的深度

然后$i$后面的回文串数只要倒着做一遍再记录一个后缀和就好了

然后记$sum$为总共的回文串数，回文串对数就是$sum*(sum-1)/2$

然后减一减就好了

1 //minamoto 2 #include
     
       3 #include
      
        4 const int N=2e6+5,P=51123987; 5 int head[N],Next[N],ver[N],edge[N],E; 6 int len[N],fail[N],cnt[N],dep[N],suf[N],p,q,tot,last; 7 char s[N],ss[N]; 8 int n,m,sum,ans; 9 inline int pls(int x,int y){
   return x+=y,x>=P?x-P:x;}10 inline int sub(int x,int y){
   return x-=y,x<0?x+P:x;}11 inline int newnode(int x){12     len[++tot]=x;return tot;13 }14 inline int getfail(int x,int n){15     while(s[n-len[x]-1]!=s[n]) x=fail[x];return x;16 }17 inline void init(){18     s[0]=-1,fail[0]=1,last=n=0;19     len[0]=0,len[1]=-1,tot=1,E=0;20     memset(cnt,0,sizeof(cnt));21 }22 inline void add(int u,int v,int e){23     ver[++E]=v,Next[E]=head[u],head[u]=E,edge[E]=e;24 }25 inline int get(int u,int e){26     for(int i=head[u];i;i=Next[i])27     if(edge[i]==e) return ver[i];return 0;28 }29 int ins(int c){30     s[++n]=c,p=getfail(last,n);31     if(!get(p,c)){32         q=newnode(len[p]+2);33         fail[q]=get(getfail(fail[p],n),c);34         add(p,q,c),dep[q]=dep[fail[q]]+1;35     }36     ++cnt[last=get(p,c)];return dep[last];37 }38 inline int calc(){39     int res=0;40     for(int i=tot;i>=2;--i)41     res=pls(res,cnt[i]),cnt[fail[i]]+=cnt[i];42     return res;43 }44 int main(){45 //    freopen("testdata.in","r",stdin);46     scanf("%d%s",&m,ss+1);47     init();for(int i=m;i;--i) suf[i]=pls(suf[i+1],ins(ss[i]-'a'));48     memset(head,0,sizeof(head));49     init();for(int i=1;i<=m;++i) ans=pls(ans,1ll*ins(ss[i]-'a')*suf[i+1]%P);50     sum=calc();51     sum=1ll*sum*(sum-1)/2%P;52     printf("%d\n",sub(sum,ans));53     return 0;54 }