CF17E：Palisection——题解

https://vjudge.net/problem/CodeForces-17E

http://codeforces.com/problemset/problem/17/E

题目大意：给一个长度为n的字符串，求不相交的回文串对数。

————————————————————————————

点击这里看大佬的题解。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 2000010

#define MOD 51123987

using namespace std;

typedef long long ll;

ll mx,id,p[*N],f[*N],g[*N];

//g[i]以i为终点的回文串个数

//f[i]以i为起点的回文串个数

char s[*N];

int main(){

    int l;

    scanf("%d%s",&l,s+);

    s[]='@';

    ll sum=;

    for(int i=l;i>=;i--)s[i*]=s[i];

    for(int i=;i<=*l+;i+=)s[i]='#';

    s[*l+]='?';

    l=*l+;

    for(int i=;i<=l;i++){

    if(mx>i)p[i]=min(p[*id-i],mx-i);

    else p[i]=;

    while(s[i-p[i]]==s[i+p[i]])p[i]++;

    if(i+p[i]>mx){

        mx=i+p[i];

        id=i;

    }

    sum+=(p[i]-)>>;

    if(i%==)sum++;

    sum%=MOD;

    }

    sum=sum*(sum-)/;

    for(int i=;i<=l;i+=){

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

    f[i+]--;

    g[i]++;

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

    }

    for(int i=;i<=l;i+=){

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

    f[i+]--;

    g[i+]++;

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

    }

    for(int i=;i<=l;i+=){

    f[i]+=f[i-];

    f[i]%=MOD;

    g[i]+=g[i-];

    g[i]%=MOD;

    }

    f[l+]=;

    for(int i=l-;i>=;i-=){

    f[i]+=f[i+];

    f[i]%=MOD;

    }

    for(int i=;i<=l;i+=){

    sum-=g[i]*f[i+]%MOD;

    sum=(sum+MOD)%MOD;

    }

    printf("%lld\n",(sum%MOD+MOD)%MOD);

    return ;

}