CF17E Palisection 差分+manacher算法

题目大意：

给定一个串$S$，询问有多少对相交的回文子串

直接做的办法：

我们先考虑求出以$i$为结尾的串的数量，这个很好统计

之后，我们再求出所有包含了点$i$的回文串的数目

这个相当于在$i$的左边加上一个等差数列，右边同理可以统计出来

二次差分后维护这些东西就可以做到$O(n)$

听起来就很难打....

考虑反面

求出所有不相交的回文子串对的数目

只需要求出所有的回文串的数目

以及以点$i$为开头的串的数目，和以点$1 ... i - 1$为结尾的串的数目

这两个也十分统计

$O(n)$即可

注意不要被"#"给多余统计了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

const int sid = 4000005;
const int mod = 51123987;

inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }
inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; }
inline int mul(int a, int b) { return 1ll * a * b % mod; }

int n, m, ans;
char s[sid], t[sid];
int r[sid], st[sid], ed[sid];

int main() {
    cin >> n;
    scanf("%s", s + 1);
    
    rep(i, 1, n)
        t[++ m] = '#', t[++ m] = s[i];
    t[++ m] = '#';
    
    r[1] = 1;
    int mr = 1, pos = 1;
    rep(i, 2, m) {
        r[i] = min(mr - i + 1, r[pos + pos - i]);
        while(i - r[i] > 0 && t[i + r[i]] == t[i - r[i]]) r[i] ++;
        if(i + r[i] - 1 > mr) mr = i + r[i] - 1, pos = i;
        st[i - r[i] + 1] ++; st[i + 1] --;
        ed[i] ++; ed[i + r[i]] --;
        inc(ans, r[i] / 2);
    }
    
    int sum = 0;
    ans = 1ll * ans * (ans - 1) / 2 % mod;
    rep(i, 1, m) {
        st[i] += st[i - 1];
        ed[i] += ed[i - 1];
        if(t[i] != '#') {
            dec(ans, mul(st[i], sum));
            inc(sum, ed[i]);
        }
    }
    
    cout << ans << endl;
    return 0;
}

原来CF是不能开int128的...