# Description

Luogu 传送门

# Solution

非常有意思的一道题。

看到回文子串，首先想到的 manacher 算法。emm…… 但是写了 manacher 之后怎么做呢？

我们发现，求相交的回文子串非常麻烦，所以直接一波正难则反，用总的回文子串数减去不相交的。

接下来考虑如何求不相交的回文子串。

我们开两个数组 $f_i$，$g_i$。$f_i$ 表示以 $i$ 为开头的回文串有多少个，$g_i$ 表示以 $i$ 为结尾的回文串有多少个。

看到标签里的前缀和，我们给 $g_i$ 做个前缀和存到 $sum_i$ 里，那么 $sum_i$ 就表示结尾是 $i$ 及以前的点的回文子串有多少个， 我们发现不相交的回文子串个数就是:

$$res = \sum\limits_{i = 1}^{n}{sum_i \times f_{i + 1}}$$

用总数减去即可。

那么 $f_i$ 和 $g_i$ 怎么求呢？

我们发现标签里的差分还没有用到标签真是好用。考虑用差分。

我们已经使用 manacher 算法求出了每个点作为回文串的中心时最长的回文半径是多少，设为 $p_i$（$p_i$ 是原字符串扩展后的新串的回文半径，长度就是原串的回文串的长度，如果不懂的话可以去学一下 manacher，这里不再赘述）。

我们发现，一个半径 $p_i$ 会形成许多回文串，分别是：

$$i - p_i + 1\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 1 \\ i - p_i + 2\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 2 \\ i - p_i + 3\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 3 \\ · \\ · \\ i - 1\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + 1$$

也就是说，我们要对 $f_{i - p_i + 1} \sim f_i$ 都 +1，同样的，对$g_i \sim g_{i + p_i - 1}$ 也都 +1。

这时我们就可以用差分来解决了，即 $f_{i - p_i + 1}++$，$f_{i + 1}--$，同时对 $g_{i}++$，$g_{i + p_i}--$。

最后循环一遍统计答案就可以啦，需要注意的是，现在我们已经把原本的字符串扩展过了，所以循环的增幅为 2。

# Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

using namespace std;

const ll N = 4e6 + 10;

const ll mod = 51123987;

ll n, ans, tot, sum;

char s[N], a[N];

ll f[N], g[N], p[N];

inline void manacher(){

    s[0] = '*', s[(n << 1) + 1] = '#';

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

        s[(i << 1) - 1] = '#', s[i << 1] = a[i];

    n = (n << 1) + 1;

    ll mx = 0, id = 0;

    for(ll i = 1; i <= n; ++i){

        if(i < mx) p[i] = min(mx - i, p[(id << 1) - i]);

        else p[i] = 1;

        while(i - p[i] >= 1 && i + p[i] <= n && s[i - p[i]] == s[i + p[i]]) p[i]++;

        if(i + p[i] > mx) mx = i + p[i], id = i;

        tot = (tot + (p[i] >> 1)) % mod;

    }

}

signed main(){

    scanf("%lld%s", &n, a + 1);

    manacher();

    for(ll i = 1; i <= n; ++i){

        f[i - p[i] + 1]++, f[i + 1]--;

        g[i]++, g[i + p[i]]--;

    }

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

        f[i] += f[i - 1], g[i] += g[i - 1];

    ans = tot * (tot - 1) / 2 % mod;

    for(ll i = 2; i <= n - 2; i += 2){

        sum = (sum + g[i]) % mod;

        ans = (ans - sum * f[i + 2] % mod + mod) % mod;

    }

    printf("%lld\n", ans);

    return 0;

}

# End