题意

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

输入格式

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

输出格式

相交的回文子串个数%51123987

题解

正难则反

可以求不相交的回文子串对数，预处理出以i开头和结尾的回文串个数。

与以i开头的回文串不相交，那么该回文串在i之前结尾。

在manacher预处理时，求的是最长回文子串，如果有以j-1开头，就有以j开头(j<i)，所以是区间修改，可以利用差分数组。

在统计答案时，只有读到原串字符才计算，统计时记录sum为以[1,i)结尾的的回文子串个数。

//补集转化，求不相交的回文串对数#include
      
       using namespace std;#define ll long longconst int mod=51123987;const int inv=25561994;const int maxn=2000005;int n;ll ans;int pl[maxn<<1];int l[maxn<<1],r[maxn<<1]; char s[maxn<<1],t[maxn];void manacher(){    s[0]='+';    for(int i=1;i<2*n;i+=2){        s[i]='#';        s[i+1]=t[i/2];    }    s[2*n+1]='#';    s[2*n+2]='-';    s[2*n+3]='\0';    n=2*n+1;    int mx=0,id=0;    for(int i=1;i<=n;i++){        if(mx>=i) pl[i]=min(mx-i+1,pl[2*id-i]);        else pl[i]=1;        while(s[i-pl[i]]==s[i+pl[i]]) pl[i]++;        if(i+pl[i]-1>mx) mx=i+pl[i]-1,id=i;        l[i-pl[i]+1]++;l[i+1]--;        r[i]++;r[i+pl[i]]--;        ans=(ans+(pl[i]>>1))%mod;//原串回文串总数         //printf("%d ",s1[i]);    }}int main(){    scanf("%d",&n);    scanf("%s",t);    manacher();    //printf("%d ",ans);    ans=(ans*(ans-1)%mod)*inv%mod;    //printf("%d ",ans);    ll sum=0;    for(int i=1;i<=n;i++){      l[i]+=l[i-1];r[i]+=r[i-1];      if(i&1) continue;      ans=(ans-sum*l[i])%mod;      sum=(sum+r[i])%mod;    }    printf("%lld",(ans%mod+mod)%mod);}
      

 

yyr讲了一种方法，没写出来。。。。还是这种方法好理解