正文

hdoj5785

IP云
IP云V管理员/0 阅读
12/02
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：略

先用题解的办法，manacher,然后tag,add数组。但是比较难办的是manacher加了新的字符。这样的话cntL和cntR不是实际的值，但是没关系，原本的字符都在奇数位置，这样cntL[i]就等于(add[i]-tag[i])/2就是真实值，具体来说不好看，我看了3个小时才明白。比如

$#a#a#a#

12345678(下标)

01234321(radius)

那么第一个a,i=3时cntL+3,i=4时cntL+5,i=5时cntL+7。实际上是+1，+2,+3的。而tag表示它被加过几次。因此1+2+3=(3+5+7-3)/2；除法用逆元。 

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,SSZ=*SZ,INF=0x7FFFFFFF,mod=;

char src[SSZ],ch[SSZ];

lon slen,clen,rd[SSZ];

lon cntr[SSZ],cntl[SSZ];

lon add[SSZ],tag[SSZ],inv;

void init()

{

    slen=strlen(src+);

    clen=;

    ch[++clen]='$';

    ch[++clen]='#';

    for(lon i=;i<=slen;++i)

    {

        ch[++clen]=src[i];

        ch[++clen]='#';

    }

}

lon ext(lon ct,lon pos,lon &maxr,lon &maxid)

{

    lon res=;

    for(lon i=pos;i<=clen;++i)

    {

        lon ll=ct-(i-ct);

        if(ch[ll]==ch[i])++res;

        else break;

    }

    return res;

}

void manacher()

{

    lon maxr=,maxid=;

    for(lon i=;i<=clen;++i)

    {

        if(i<=maxr)

        {

            lon rf1=maxid-(i-maxid);

            lon rf2=maxid-(maxr-maxid);

            lon ll=(rf1-rd[rf1]+);

            if(ll>rf2)rd[i]=rd[rf1];

            else rd[i]=(maxr-i+)+ext(i,maxr+,maxr,maxid);

        }

        else

        {

            rd[i]=ext(i,i,maxr,maxid);

        }

        if(i+rd[i]->maxr)

        {

            maxr=i+rd[i]-;

            maxid=i;

        }

    }

}

void work()

{

    manacher();

    for(lon i=;i<=clen;++i)

    {

        lon ll=i-rd[i]+,rr=i+rd[i]-;

        ++tag[ll],add[ll]+=(i+rd[i]-)+;

        --tag[i+],add[i+]-=i;

    }

    for(lon i=;i<=clen;++i)

    {

        //cout<<tag[i]<<" "<<add[i]<<endl;

        tag[i]+=tag[i-];

        add[i]+=add[i-]-tag[i];

        add[i]%=mod;

        cntr[i]=(add[i]-tag[i])*inv%mod;

        //cout<<cntr[i]<<endl;

    }

    for(lon i=;i<=clen+;++i)

    {

        tag[i]=add[i]=;

    }

    for(lon i=;i<=clen;++i)

    {

        lon rr=i+rd[i]-,ll=i-rd[i]+;

        ++tag[rr],add[rr]+=(i-rd[i]+)-;

        --tag[i-],add[i-]-=i;

    }

    for(lon i=clen;i>=;--i)

    {

        tag[i]+=tag[i+];

        add[i]+=add[i+]+tag[i];

        add[i]%=mod;

        cntl[i]=(add[i]-tag[i])*inv%mod;

    }

    for(lon i=;i<=clen+;++i)

    {

        tag[i]=add[i]=;

    }

    lon res=;

    for(lon i=;i<clen;i+=)

    {

        //cout<<cntl[i]<<" "<<cntr[i+1]<<endl;

        res+=cntl[i]*cntr[i+];

        res%=mod;

    }

    res=(res+mod)%mod;

    cout<<res<<endl;

    for(lon i=;i<=clen+;++i)

    {

        cntl[i]=cntr[i]=rd[i]=;

    }

}

void ex_gcd(lon a,lon b,lon &x,lon &y,lon &d)

{

    if(b==)

    {

        d=a,x=,y=;

    }

    else

    {

        ex_gcd(b,a%b,y,x,d);

        y-=(a/b)*x;

    }

}

int main()

{

    //std::ios::sync_with_stdio(0);

    //freopen("d:\\1.txt","r",stdin);

    lon x,y,d;

    ex_gcd(,mod,x,y,d);

    inv=x;

    lon casenum;

    //cin>>casenum;

    //cout<<casenum<<endl;

    //for(lon time=1;time<=casenum;++time)

    for(int time=;scanf(" %s",src+)!=EOF;++time)

    {

        init();

        work();

    }

    return ;

}

相关阅读

目录[+]