题意翻译
给定一个长度为n的小写字母串。问你有多少对相交的回文子 串（包含也算相交） 。 输入格式
第一行是字符串长度n(1<=n<=2*10^6)，第二行字符串 输出格式
相交的回文子串个数%51123987
题解
首先，我们要知道一个串有多少个回文串。
1.manacher，
枚举回文中心可以计算出所有的回文串个数
(i+p[i]-1)-(i-p[i]+1)+1
然后我们怎么知道多少相交的回文串呢？
计数问题要转化成有分界点的问题，便于利用乘法加法原理等。——lyd
这个相交显然不好处理，也没有分界点。
所以采用容斥。
2.容斥，所有的回文串对数-不相交的对数
不相交的话，分界点一下就出来了。我们可以枚举分解点试试。
因为这样便于划分成区间处理。
而直接相交处理不容易。
3.枚举分界点统计
①
c[x][0]以x开始的回文串个数，c[x][1]以x为末尾的回文串个数
这两个可以区间加，差分处理。
具体来说，一个点为中心的所有回文串，会给(i-p[i]+1)~(i)位置开始的回文串多一个。c[x][1]同理。
这里的差分，不用树状数组....并不需要动态维护修改查询
直接数组差分即可。最后从左到右累加，一边统计c[x][0/1]
然后令，pre[x]，为c[x][1]的前缀和
②
对于枚举的分界点i(2<=i<=n) ,ans-=pre[i-1]*c[i][0]
根据回文串开始和结束位置的唯一性，这样一定不重不漏。
相当于把每个字符串和前面不相交的字符串都统计了一遍。
代码：注意%=mod
#include<bits/stdc++.h>
#define ri register int
#define il inline
using namespace std;
typedef long long ll;
const int N=+;
const int mod=;
int n,m;
int p[*N];
char a[N],b[*N];
il void manacher(){
p[]=;
int mx=,id=;
for(ri i=;i<=m;i++){
p[i]=min(p[*id-i],mx-i);
if(p[i]<) p[i]=;
int j=i-p[i],k=i+p[i];
while(j>=&&k<=m&&b[j]==b[k]){
p[i]++;
j--;k++;
}
if(i+p[i]->mx){
mx=i+p[i]-;
id=i;
}
}
}
ll f[N],g[N];
ll ans,tot,sum;
ll c[N][],pre[N];
il void add1(int x,ll c){
f[x]+=c;
}
il void add2(int x,ll c){
g[x]+=c;
}
signed main()
{
scanf("%d",&n);
scanf("%s",a+);
b[++m]='#';
for(ri i=;i<=n;i++){
b[++m]=a[i];
b[++m]='#';
}
manacher();
for(ri i=;i<=m;i++){
if(i&) (tot+=p[i]/)%=mod;//%mod;//#
else (tot+=p[i]/)%=mod;//%mod;//not
}
ans=(tot*(tot-)/)%mod;//%mod;
for(ri i=;i<=n;i++){
add1(i-p[i*]/+,(ll)),add1(i+,(ll)-);
if(i!=n) add1(i-p[i*+]/+,(ll)),add1(i+,(ll)-); } for(ri i=;i<=n;i++){
c[i][]=(c[i-][]+f[i])%mod;
} for(ri i=;i<=n;i++){
add2(i,(ll)),add2(i+(p[i*]/),(ll)-);
if(i!=n) add2(i+,(ll)),add2(i+p[i*+]/+,(ll)-);
}pre[]=;
for(ri i=;i<=n;i++){
c[i][]=(c[i-][]+g[i])%mod;
pre[i]=(pre[i-]+c[i][])%mod;
if(i>=){
ll now=(pre[i-]*c[i][])%mod;
ans=(ans+mod-now)%mod;
}
}
printf("%lld",ans);
return ;
}
总结：
突破口：容斥。划分分界点统计。