lessons/参考实现/04-KMP与Manacher/CodeForces-17E.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; string s; cin >> n >> s;
    vector<int> d1(n), d2(n);
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = i > r ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
        d1[i] = k;
        if (i + k - 1 > r) l = i - k + 1, r = i + k - 1;
    }
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = i > r ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        d2[i] = k;
        if (i + k - 1 > r) l = i - k, r = i + k - 1;
    }

    vector<long long> start_diff(n + 1), end_diff(n + 1);
    auto add = [&](vector<long long> &diff, int l, int r) {
        if (l > r) return;
        ++diff[l]; --diff[r + 1];
    };
    long long palindromes = 0;
    for (int i = 0; i < n; ++i) {
        palindromes += d1[i] + d2[i];
        add(start_diff, i - d1[i] + 1, i);
        add(end_diff, i, i + d1[i] - 1);
        add(start_diff, i - d2[i], i - 1);
        add(end_diff, i, i + d2[i] - 1);
    }

    constexpr long long mod = 51123987;
    long long a = palindromes, b = palindromes - 1;
    if (a % 2 == 0) a /= 2; else b /= 2;
    long long all_pairs = (a % mod) * (b % mod) % mod;

    long long starts_here = 0, ends_here = 0, ended_before = 0, disjoint = 0;
    for (int i = 0; i < n; ++i) {
        starts_here += start_diff[i];
        ends_here += end_diff[i];
        disjoint = (disjoint + (starts_here % mod) * (ended_before % mod)) % mod;
        ended_before += ends_here;
    }
    cout << (all_pairs - disjoint + mod) % mod << '\n';
}