题意:略
先用题解的办法,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 ;
}