CodeForces - 17E Palisection

哇塞感觉从没有做过这么老的比赛的题。（好奇妙）

这里记录一下我的思路：用线段树。我们算出每个点的最长回文长度后，将\([i-p[i]+1,i+p[i]-1]\)加上一。我们尝试将每个区间内的小回文串查询，易得查出来的值减去小区间的长度就是与其匹配的个数。

例如下面这段区间：

00011

我们知道，最右边的那个一代表着一个小回文串可以延伸到此区间，也就是两个回文串??。

当然我是在瞎\(bibi\)，这显然会超时。。。

好了咱们进入正题：可以用差分来解决。仔细想想，我们用线段树，其实有一部分是因为想要快速给区间赋值。我们给\([l,r]\)加上一，可以将\(a[l]\)加上一，将\(a[r+1]\)减去一，再做一个前缀和，不是正好可以赋值吗？

正难则反。我们先统计两两子串的组合，再减去不??的个数就行了。

设\(i<j\)，我们发现，以\(i\)结尾的子串是不可能与以\(j\)开头的子串??的。

设\(r[i]\)为以\(i\)为结尾的子串个数，\(l[i]\)是以大于等于\(i\)的编号为开头的子串个数。

那么不??的子串就可以表示了：\(Σr[i]*l[i+1]\)。

然后，就成啦！

本蒟蒻第一次用\((a+b)\%=mod\)写成了\((a+b)\%mod\)，样例竟然过了，卡了蒟蒻半个小时。。。

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

const int N = 2e6 + 5, mod = 51123987, inv2 = 25561994; 

long long ans;
int n, p[N << 1], s[N << 1], ori[N], l[N << 1], r[N << 1], lef[N], rig[N];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) > '9' || s < '0') {
        if(s == '-') f = -1;
        if(s == EOF) exit(0);   
    }
    while(s <= '9' && s >= '0') {
        x = (x << 1) + (x << 3) + (s ^ 48);
        s = getchar();
    }
    return x * f;
}

int init() {
    s[0] = -1; s[1] = -3;
    int j = 2;
    for(int i = 0; i < n; ++ i) {
        s[j ++] = ori[i];
        s[j ++] = -3;
    }
    s[j] = -2;
    return j;
}

void manacher() {
    n = init();
    int ans = -1, R = 0, mid;
    for(int i = 1; i < n; ++ i) {
        if(i < R) p[i] = min(p[(mid << 1) - i], R - i);
        else p[i] = 1;
        while(s[i - p[i]] == s[i + p[i]]) ++ p[i];
        if(R < i + p[i]) {
            R = i + p[i];
            mid = i;
        }
    }
}

long long fix(const long long x) {return (x % mod + mod) % mod;}

int main() {
    char ch[N];
    int tmp;
    n = read(); scanf("%s", ch);
    for(int i = 0; i < n; ++ i) ori[i] = ch[i] - 'a';
    tmp = n;
    manacher();
    for(int i = 1; i < n; ++ i) {
        ++ l[i - p[i] + 1]; -- l[i + 1];
        ++ r[i]; -- r[i + p[i]];
    }
    for(int i = 1; i < n; ++ i) {
        (ans += p[i] >> 1) %= mod;
        (l[i] += l[i - 1]) %= mod; (r[i] += r[i - 1]) %= mod;
        if(s[i] != -3) lef[i - 1 >> 1] = l[i], rig[i - 1 >> 1] = r[i];
    }
    for(int i = tmp - 2; i >= 0; -- i) (lef[i] += lef[i + 1]) %= mod;
    ans = ans * fix(ans - 1) % mod * inv2 % mod;
    for(int i = 0; i < tmp; ++ i)
        ans = fix(ans - 1ll * rig[i] * lef[i + 1] % mod);
    printf("%lld\n", ans);
    return 0;
}

CodeForces - 17E Palisection

原文：https://www.cnblogs.com/AWhiteWall/p/12365595.html