Card space PAM, there is no PAM in 2010, so they are all horse-drawn carts

As we all know, PAM has a very good time complexity, but the space complexity lj is not good

But this question card space, so you have to use the adjacency list PAM

Think first

The title requires intersecting pairs of palindromic substrings, which is hard to do

So we find the complement, find the pair of disjoint palindromic substrings, and then subtract the total number.

The method is similar to the longest double palindromic substring above

Build a PAM forward and reverse, save the number of palindromic substrings at the end of the position, and then change the addition to multiplication

Understand it for yourself, it's pretty simple.

Now let's talk about the adjacency list PAM

Note: The adjacency list PAM does not make the space smaller, but exchanges time for space

We note the edge structure\(line\)

Save \(3\) pieces of information: \(nx,to,w\) respectively represent the previous edge, the node number to which this edge leads, and which character this edge represents

The array \(fir[i]\) represents the number of the last edge extended by \(i\) (header type

When we are looking for the \(v\) son of \(u\)

We search like an adjacency list until there is an edge \(w==v\)

Can't find the remember finger

int getson(int u,int v){
	for(int i=u;i!=-1;i=l[i].nx)
		if(l[i].w==v)return l[i].to;
	return -1;
}

When building points, build edges

void insert(int u,int i){
	int Fail=getfail(pre,i),ls=getfail(fail[Fail],i);
	if(getson(fir[Fail],u)==-1){
		if(getson(fir[ls],u)==-1)fail[++tot]=0;		//can't find finger root
		else fail[++tot]=getson(fir[ls],u);	//found it
		l[++cnt]=(line){fir[Fail],tot,u};fir[Fail]=cnt;		//border
		len[tot]=len[Fail]+2;
		ans[tot]=ans[fail[tot]]+1;		//Number of palindromic substrings at the end
		pre=tot;
	}else 
	pre=getson(fir[Fail],u);
}

However, in fact, you still can't pass, you have to continue to press space, save a bunch of arrays and you can pass!

Total code:

#include<bits/stdc++.h>
#define maxn 2000005
#define mod 51123987
using namespace std;
char s[maxn];
int slen,b[maxn];
long long res;
int fail[maxn],len[maxn],ans[maxn],fir[maxn];
struct line{int nx,to,w;}l[maxn];
int tot,pre,cnt;
void init(){
	memset(fir,-1,sizeof(fir));cnt=0;
	fail[0]=1;len[1]=-1;tot=1;pre=0;
}
int getfail(int x,int i){
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
int getson(int u,int v){
	for(int i=u;i!=-1;i=l[i].nx)
		if(l[i].w==v)return l[i].to;
	return -1;
}
void insert(int u,int i){
	int Fail=getfail(pre,i),ls=getfail(fail[Fail],i);
	if(getson(fir[Fail],u)==-1){
		if(getson(fir[ls],u)==-1)fail[++tot]=0;
		else fail[++tot]=getson(fir[ls],u);
		l[++cnt]=(line){fir[Fail],tot,u};fir[Fail]=cnt;
		len[tot]=len[Fail]+2;
		ans[tot]=ans[fail[tot]]+1;
		pre=tot;
	}else 
	pre=getson(fir[Fail],u);
}
int main(){
	int n;
	scanf("%d",&n);
	scanf("%s",s);slen=strlen(s);init();
	reverse(s,s+slen);
	for(int i=0;i<slen;i++)insert(s[i]-'a',i),b[slen-i-1]=ans[pre];
	for(int i=slen-1;i>=0;i--)b[i]+=b[i+1],b[i]%=mod;
	reverse(s,s+slen);init();
	for(int i=0;i<slen-1;i++){
		insert(s[i]-'a',i);int x=ans[pre];
		res+=(1ll*x*b[i+1])%mod,res%=mod;
	}
	printf("%lld\n",((1ll*b[0]*(b[0]-1)/2ll)%mod-res+mod)%mod);
	return 0;
}