Description：

给一个字符串，求有相交部分的回文子串对有多少。

$1\le n \le 4000000$

Solution：

正难则反，相交的情况很复杂，不相交的更简单，考虑计算出所有的回文串个数 $sum$ 再用 $C^{sum}_2-$ 不相交的回文串对个数。

先用 $manacher$ 预处理出所有位置的最长回文半径，然后计算两个数组， $lef[i]$ 和 $rig[i]$ 分别表示以 $i$ 为左 $/$ 右端点的回文串个数那么总的不相交回文串对个数就是 $\begin{align}\sum_{i<j}rig[i]\times lef[j]\end{align}$ ，但这样计算还是太慢了，把 $lef$ 数组做一个后缀和，答案就变成了 $\begin{align}\sum_{i=1}^{n-1}rig[i]\times lef\_sufsum[i+1]\end{align}$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 51123987

#define INV 25561994

int n;

#define MAXN 4000010

char c[MAXN];

int h[MAXN];

char s[MAXN];

int tot = 0;

typedef long long ll;

ll lef[MAXN],rig[MAXN];

int main()

{

	scanf("%d",&n);

	scanf("%s",c + 1);

	s[++tot] = '#';

	for(int i = 1;i <= n;++i)

	{

		s[++tot] = c[i];

		s[++tot] = '#';

	}

	int pos = 1,maxr = 1;

	ll sum = 0;

	for(int i = 1;i <= tot;++i)

	{

		if(maxr > i)h[i] = min(h[pos * 2 - i],maxr - i + 1);

		else h[i] = 1;

		while(i - h[i] >= 1 && i + h[i] <= tot && s[i - h[i]] == s[i + h[i]])++h[i];

		if(i + h[i] - 1 > maxr)

		{

			maxr = i + h[i] - 1;

			pos = i;

		}

		sum = (sum + h[i] / 2) % MOD;

	}

	for(int i = 2;i < tot;++i)

	{

		if(i & 1)

		{

			lef[(i - h[i] + 2) / 2]++;lef[i / 2 + 1]--;

			rig[i / 2 + 1]++;rig[(i + h[i] - 1) / 2 + 1]--;

		}

		else

		{

			lef[(i - h[i] + 2) / 2]++;lef[i / 2 + 1]--;

			rig[i / 2]++;rig[(i + h[i]) / 2]--;

		}

	}

	for(int i = 1;i <= n;++i)lef[i] = (lef[i - 1] + lef[i]) % MOD;

	for(int i = 1;i <= n;++i)rig[i] = (rig[i - 1] + rig[i]) % MOD;

	for(int i = n - 1;i >= 1;--i)lef[i] = (lef[i + 1] + lef[i]) % MOD;

	long long ans = 0;

	for(int i = 1;i < n;++i)

	{

		ans = (ans + rig[i] * lef[i + 1] % MOD) % MOD;

	}

	ans = (sum * (sum - 1) % MOD * INV % MOD - ans + MOD) % MOD;

	cout << ans << endl;

	return 0;

}